[ 백준 - 1253 ] 좋다 (Python)

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

1253번: 좋다

문제를 보고 고민하다가 결국 다 범위를 좁혀가면서 확인을 해봐야 할 것 같다는 생각이 들었다.

투 포인터 방식으로 문제를 풀어 봤는데, 계속해서 반례에 걸려서 반례들을 찾느라고 시간을 썼다.

 

[ 📌 고려사항 ]

1. 음수가 있을 수 있음  |A| <= 1,000,000,000 이기 때문에 음수도 포함한다.
2. 동일한 수가 있을 수 있음 ex) 0 0 0 0
   • 0 + 0 = 0 이다.
   • 본인(0) + 0 = 0
   • 본인(0) + 0 = 본인(0)
3. 위 이유로 본인(선택한 리스트의 요소)는 제외 시켜줘야 한다.

 

[ 📌 코드 흐름 ]

1. 현재 선택한 요소를제외한 리스트를 만든다.

⚙︎ 본인을 제외한 리스트에서 선택한 두 요소의 합이 '좋다'를 만족하는 수인지 찾을 수 있게 해주는 작업

temp = num_list[:num] + num_list[num + 1:]

2. 투 포인터 알고리즘 수행

    2 - 1. '좋다'의 수를 찾는다면 종료한다.

    2 - 2. 합이 현재 선택한 요소보다 작다면 합의 크기를 키우기 위해서 left를 + 1

    2 - 3. 합이 현재 선택한 요소보다 크다면 합의 크기를 줄이기 위해서 right를 - 1

 

[ 📌 코드 - Python ]

지금 보니까 num -> index로 바꿔야 코드를 읽는데 더 편할 것 같은데 변수 이름을 잘못 준 것 같다.

import sys
input = sys.stdin.readline

N = int(input())
num_list = list(map(int, input().strip().split()))
ans = 0

num_list.sort()

for num in range(N):
    temp = num_list[:num] + num_list[num + 1:]
    left, right = 0, len(temp) - 1

    while left < right:
        lr_sum = temp[left] + temp[right]

        if lr_sum == num_list[num]:
            ans += 1
            break
        elif lr_sum < num_list[num]:
            left += 1
        else:
            right -= 1

print(ans)