1253
1253번: 좋다
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
www.acmicpc.net
👾접근
주어지는 수의 범위가 절댓값이 1,000,000,000 이하인 정수인 점 과 정수 중복도 가능하다는 점을 알고 있어야 한다..(이거 고려못하고 중복없는 양의 정수로 풀어서 헤맸다)
즉, 체크되는 수를 제외한 두 수의 합이 체크되는 수와 같기만 하면 된다.
좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn) 이 되어야 함 => 정렬과 투포인터 사용해보기
리스트를 정렬한 후 좋은 수 여부를 체크할 위치를 지정하고
해당 인덱스를 제외하고 양쪽 끝 인덱스로 s 와 e 투 포인터를 지정해준다.
투 포인터 이동 원칙
- lst[s] + lst[e] == check ; good += 1 ; break
- lst[s] + lst[e] > check : e -= 1
- lst[s] + lst[e] < check : s += 1
풀이
import sys
input = sys.stdin.readline
N = int(input())
lst = list(map(int, input().split()))
lst.sort()
good = 0
for i in range(N):
# 합 확인할 정수 지정
check = lst[i]
print()
print(f'[ check : {check} , i : {i} ]')
s = 0 #시작 포인터
e = N-1 #종료 포인터
while s < e :
if lst[s] + lst[e] == check :
print(f'sum:{lst[s] + lst[e]} ({s},{e})', end= " → ")
if s != i and e !=i:
print(f'탈출 성공!!')
good += 1
break
elif s == i : # 시작 포인터가 check 인 경우 예외처리
print(f'탈출 실패 (s == i) : s ++')
s+= 1
elif e == i : # 종료 포인터가 check 인 경우 예외처리
print(f'탈출 실패 (e == i) : e --')
e -= 1
elif lst[s] + lst[e] < check :
print(f'sum:{lst[s] + lst[e]} ({s},{e}) s ++')
s+=1
else:
print(f'sum:{lst[s] + lst[e]} ({s},{e}) e --')
e -= 1
print(good)
## 입출력 예
4
[0, 1, 2, 3]
[ check : 0 , i : 0 ]
sum:3 (0,3) e --
sum:2 (0,2) e --
sum:1 (0,1) e --
[ check : 1 , i : 1 ]
sum:3 (0,3) e --
sum:2 (0,2) e --
sum:1 (0,1) → 탈출 실패 (e == i) : e --
[ check : 2 , i : 2 ]
sum:3 (0,3) e --
sum:2 (0,2) → 탈출 실패 (e == i) : e --
sum:1 (0,1) s ++
[ check : 3 , i : 3 ]
sum:3 (0,3) → 탈출 실패 (e == i) : e --
sum:2 (0,2) s ++
sum:3 (1,2) → 탈출 성공!!
이 문제는 반례를 봐야지만 문제 해결법이 보이는 거 같다...
누군가 올려놓은 반례들..
2
0 0
out : 0
3
0 3 3
out : 2
2
0 1
out : 0
3
0 0 0
out : 3
4
0 1 2 3
out : 1
3
0 -5 5
out : 1
'🏷️CS > Algorithm' 카테고리의 다른 글
코테에 사용하기 좋은 라이브러리 기능 (0) | 2023.04.30 |
---|---|
시간 복잡도 (0) | 2023.04.27 |
[백준] 1940 (주몽) (0) | 2023.03.01 |
[백준] 2018(수들의 합5) (0) | 2023.02.25 |
[백준] 10986 (나머지 합) (0) | 2023.02.25 |