문제
정답 소스코드 (Python)
n=int(input())
arr=list(map(int,input().split()))
arr.sort()
count=0
for i in range(n):
left,right=0,n-1 #기본 left, right설정
#반례 처리 N은 자기자신을 제외한 다른 수 이기 때문에
if i==0:left+=1
if i==n-1:right-=1
#투포인터 탐색
while left<right:
compare=arr[left]+arr[right]
if compare>arr[i]:
right-=1
if right==i:right-=1 #반례 처리 N은 자기자신을 제외한 다른 수 이기 때문에
elif compare<arr[i]:
left+=1
if left==i:left+=1 #반례 처리 N은 자기자신을 제외한 다른 수 이기 때문에
# 같다면
else:
count+=1
break
print(count)
풀이 (Python)
Point 1) 투포인터
#투포인터 탐색
while left<right:
compare=arr[left]+arr[right]
if compare>arr[i]:
right-=1
if right==i:right-=1 #반례 처리 N은 자기자신을 제외한 다른 수 이기 때문에
elif compare<arr[i]:
left+=1
if left==i:left+=1 #반례 처리 N은 자기자신을 제외한 다른 수 이기 때문에
# 같다면
else:
count+=1
break
형태는 이분탐색과 비슷하지만, mid값을 통한 left, right값 변경이 아닌 두 자연수의 합을 compare변수로 둔 후 비교를 하였다. 이때 arr는 오름차순으로 정렬되어 있기 때문에 두 수의 합인 compare값이 작아지려면 right값을 감소해야 한다.
반대로 compare값이 커지려면 left값을 올려주어야 한다.
Point 2) 자신이 아닌 다른 수
이 문제에서 가장 걸림돌이 되는 것은 "자기 자신이 아닌", "다른 두 수"이다. 이를 해결하기 위해 생각보다 많은 것을 생각할 수 있어서 좋은 문제였다.
left,right=0,n-1 #기본 left, right설정
#반례 처리 N은 자기자신을 제외한 다른 수 이기 때문에
if i==0:left+=1
if i==n-1:right-=1
투포인터 탐색 전 초기값도 i값에 따라 left와 right 초기값설정을 해주어야 한다. i가 n-1인 경우 right가 n-1이면 "자기 자신을 포함"하기 때문이다.
while left<right:
투포인터 탐색에서 left <=right가 아닌 left <right인 이유는 left와 right가 같아지는 경우를 없애기 위함이다.
left와 right가 같아지는 경우 "서로 다른 두 수의 합"이 아닌 "같은 두 수의 합"이 될 수도 있었기 때문이다.
if compare>arr[i]:
right-=1
if right==i:right-=1 #반례 처리 N은 자기자신을 제외한 다른 수 이기 때문에
i번째와 right가 같아지는 경우 "자기 자신을 포함" 하는 경우이기 때문에 같아지면 right에서 -1을 한번 더 해주었다.
left도 마찬가지로 예외를 처리해 주었다.
'Baekjoon' 카테고리의 다른 글
[백준] 2206번 벽 부수고 이동하기 (파이썬) (1) | 2024.02.10 |
---|---|
[백준] 1205번 등수 구하기 (파이썬) (1) | 2024.02.10 |
[백준] 5585번 거스름돈 (파이썬) (0) | 2024.02.07 |
[백준] 4796번 캠핑 (파이썬) (1) | 2024.02.07 |
[백준] 11399번 ATM (파이썬) (1) | 2024.02.06 |