백준 1253 : 좋다 (Python)

본문 링크

import sys
input=sys.stdin.readline

N=int(input())
L=sorted(list(map(int,input().split())))

count=0

for i in range(N):

    start=0 ; end=N-1
    while start<end:

        if L[start]+L[end]==L[i]:
            if start==i:
                start+=1
            elif end==i:
                end-=1
            elif start!=i and end!=i:
                count+=1
                break
        elif L[start]+L[end]>L[i]:
            end-=1
        else:
            start+=1
print(count)

📌 어떻게 문제에 접근할 것인가?

$N$ 개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
$N$ 개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.

이 문장을 보자마자 투 포인터 문제임을 확신할 수 있었다.
두 수의 합이 어떤수가 되는지 확인하는 문제이기 때문이다.

📌 어떻게 투 포인터를 적용시킬것인가?

리스트 $L$ 을 입력받고 정렬해준다. 이후 리스트 길이만큼 반복문을 돌려주어서
L[start] 와 L[end] 의 합이 L[i] 와 같은 모든 경우를 찾는다.

이때 start 와 end 는 서로 다르면서 L[i] 의 위치만 서로 다르면 좋은 수가된다.

예를 들어 0 0 0 3 3 3 3 라는 배열이 있다고 하자.

1번째 0 이 좋은수가 되는 이유는 2,3 번쨰 값의 합이 0 이기 때문이다.
2번째 0 이 좋은수가 되는 이유는 1,3 번째 값의 합이 0 이기 때문이다.

따라서 위 배열의 좋은 수의 개수는 총 7개 이다.

그러므로 start=0 , end=N-1 로 무조건 고정을 시켜준 후에
만약 L[start] 나 L[end] 값의 합이 0 이지만 L[i] 의 위치와 같다면 다시한번 탐색해주어야한다.

투 포인터에서는 두 수의 합이 어떤수보다 큰지 또는 작은지에 따라 이동을 해야하는데
3번째 0은 1번쨰 0 + 2번째 0 이런식으로 성립되므로
2번째 0 + 3번째 0의 합이 0이라고 단순히 좋은수라 판별해서는 안된다.

따라서 start==i 일때 start+=1 , end==i 일때 end-=1 을 해준다.
그리고 L[start]+L[end]==L[i] 이면서 start!=i and end!=i 일때 좋은수가 성립된다.

✅ 코드에서 중요한 부분

• 리스트는 입력받고 정렬해준다
• 좋은 수는 다른 두 수의 합으로 나타내야 한다.