[백준] 1253번 - 좋다 (파이썬)

https://www.acmicpc.net/problem/1253

 

# 좋다
import sys
input = sys.stdin.readline
N = int(input())
arr = list(map(int, input().split()))
arr.sort()

result = 0
for i, num in enumerate(arr):
    temp = arr[:i]+arr[i+1:]
    left, right = 0, len(temp)-1
    while left < right:
        if temp[left]+temp[right] > num:
            right -= 1
        elif temp[left]+temp[right] < num:
            left += 1
        else:
            result += 1
            break

print(result)

 

투포인터
1. 입력을 받고 정렬을 해준다.
2. arr의 각 수 num마다 num을 제외한 리스트 temp를 이용해서 투포인터 실행
    - 정렬된 상태이므로 num보다 작으면 left+=1, num보다 크다면 right +=1
    - num이면 num은 '좋은 수' result+=1, break
3. result 출력

 

문제를 잘 읽지 않아서 76%에서 틀렸다. 아래는 반례이다.

input
5
0 0 2 2 2
output
3

문제를 잘 보면 '어떤 수가 다른 두 수의 합으로 표현이 되면 좋은 수'라고 돼있다.

다른 두 수의 합이다. 따라서 투포인터를 할 때, 자기 자신을 제외해 주어야 한다.

즉 temp리스트를 슬라이싱으로 i를 제외하고 만들어 준 상태로 진행해야 한다.

그러지 않을 경우 위 반례에서 0+0=0으로 0이 좋은 수에 포함이 되어 output이 5가 나오게 된다.