[백준] 1253 좋다

문제

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

입력

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

출력

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

내 풀이

import sys
input = sys.stdin.readline

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

good = 0
for i in range(n):      
    x = nums[i]    # 인덱스로 하는 이유 : 같은 숫자라도 다른 위치에 있다면 다른 수로 간주
    left = 0
    right = n-1
    while left < right:
        if i == left:
            left += 1
            continue
        if i == right:
            right -= 1
            continue

        sum1 = nums[left] + nums[right]
        if sum1 == x:
            good += 1
            break
        elif sum1 > x:
            right -= 1
        else:    # sum1 < x
            left += 1

print(good)

시간 복잡도 → $O(N^2)$
nums.sort()에서 $O(N\,log\,N)$
투 포인터는 한 번 수행될 때 최대 $O(N)$ 이 소요되는데 for 문안에서 실행되므로 $O(N^2)$
따라서 최종 시간 복잡도는 $O(N^2)$
공간 복잡도 → $O(N)$
$\because$ nums 리스트 사용

코멘트

두 수를 더해서 그 수가 나오는지를 확인해야 하므로 투 포인터를 이용해서 문제를 풀어야겠다는 감을 잡았다. 여기서 주의할 점은 자기 자신을 두 수 중 하나로 사용하면 안되므로 i == left 일 때와 i == right일 때 탐색을 하지 않도록 해야 한다는 것이다. 단순히 탐색을 하지 않을 뿐만 아니라 left += 1, right -= 1을 해줘서 포인터를 움직여야 무한 루프에 빠지지 않을 수 있다.

투 포인터 문제를 풀 때 반드시 오름차순(혹은 문제에 따라 내림차순)으로 정렬한 뒤에 탐색을 해야한다는 것을 잊지 말자.

[백준] 1253 좋다

문제

입력

출력

내 풀이

코멘트

References