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

1253번: 좋다

문제

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

풀이 설계

• 먼저 정렬을 한다.
• for문으로 다른 두 수의 합이 해당 숫자가 되는지 확인한다.
• 투 포인터 알고리즘을 사용하여 양끝에서부터 시작하여 두 수를 찾는다.
• 현재 i인지 확인하고 중복 여부를 확인하여 처리한다.

풀이

n=int(input())
lst=list(map(int, input().split()))
lst.sort()

cnt=0
for i in range(n):
    target=lst[i]
    st = 0
    ed = n - 1
    while st<ed:
        if lst[st]+lst[ed]==target:
            if st!=i and ed!=i:
                cnt+=1
                break
            elif st==i:
                st+=1
            elif ed==i:
                ed-=1
        elif lst[st]+lst[ed]<target:
            st+=1
        elif lst[st] + lst[ed] > target:
            ed-=1
print(cnt)

후기

• 다른 풀이를 몇가지 찾아봤는데 대부분 투 포인터를 사용했다.