[solved.ac 골드4] 1253_좋다 (파이썬, 투 포인터)

 

제한 사항

 

문제

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

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

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

입력

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

출력

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

예제

힌트

3,4,5,6,7,8,9,10은 좋다.

 

---

나의 풀이

문제 접근은 어렵지 않았다. 투 포인터의 전형적인 유형인 것 같다.

그러나 디테일한 부분을 놓쳐 여러 시도 끝에 성공한 문제이다.

다음 4가지 상황을 주의하자

1. 입력 받은 숫자들을 정렬했는가
2. 숫자 목록에 음수가 포함되었다는 사실을 알고 있는가
3. 수의 위치가 다르면 값이 같아도 다른 수라는 조건을 고려했는가
4. 투 포인터로 검사할 때 현재 검사하고자 하는 숫자는 제외했는가

 

나는 위 4가지 사항 중 2번과 4번 상황 때문에 고전했다.

 

우선 처음 접근했을 때는 시간 복잡도를 줄이고자 현재 검사하고자 하는 숫자보다 작은 숫자에서만 확인했었다.

그러나 숫자 사이에 음수가 있는 경우 [-3, -1, 3, 4] 의 상황에서 3을 검사할 때 [-3, -1] 에서만 검사했었는데 [-1, 4] 와 같이 3보다 큰 수가 찾아질 수 있다는 점 때문에 틀리게 되었다.

그래서 새로 바꾼 코드에서는 전체 리스트를 확인했는데 여기서도 문제가 발생했다.

 

숫자 사이에 0이 있는 경우 자기 자신도 서로 다른 수 두 개 중 하나가 될 수 있다는 점이다.

예를 들어 [-1, 0, 3, 5]가 있을 때 3은 좋은 숫자가 아니어야 하지만 전체 리스트를 검사했다 보니 [0, 3]이 서로 다른 두 수로 잡혀 3이 좋은 수가 되어서 틀린 답이 되어버린 것이다.

그래서 리스트에서 현재 검사하는 수는 제외하고 검사했다.

 

전체 코드

n = int(input())
nums = sorted(map(int, input().split()))

answer = 0


def two_pointer(li, target):
    global answer

    start, end = 0, len(li) - 1

    while start < end:
        s = li[start] + li[end]
        if target == s:
            answer += 1
            return
        elif target > s:
            start += 1
        elif target < s:
            end -= 1


for i in range(n):
    two_pointer(nums[:i] + nums[i+1:], nums[i])

print(answer)

 

채점 결과