[백준/Python] 1253 좋다

📌문제 탐색하기

• N(1 ≤ N ≤ 2,000)개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있으면 "좋다(GOOD)"고 표현
• N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 구하기
  • 수의 위치가 다르면 값이 같아도 다른 수
  • 수의 범위는 (|n| ≤ 1,000,000,000)

해당 문제를 해결하기 위해서는 수들을 오름차순 정렬하고 순차적으로 숫자를 확인하면서, 나머지 숫자들 중 두 개의 숫자를 골라 두 숫자의 합이 현재 확인 중인 숫자가 되는지 알아내야 한다. '두 개의 숫자'의 합을 구해야 하므로 두 개의 점의 위치를 기록하는 투 포인터를 사용해서 풀 수 있다.

투포인터 알고리즘의 시간복잡도는 O(N)이므로 문제에서 원하는 답을 구하려면 최악의 경우 O(2,000)(모든 숫자에 대해서)*O(2,000)(투포인터 수행) = O(4,000,000)이므로 시간 내에 풀이가 가능하다.

 

📌코드 설계하기

1. 숫자의 개수 N을 입력받는다.
2. 숫자들을 리스트 numbers로 입력받아 저장하고, 오름차순 정렬한다.
3. 좋은 수의 개수를 저장할 변수 count를 0으로 초기화한다.
4. numbers에 저장된 숫자를 하나씩 탐색하며, 투 포인터 알고리즘을 통해 이전 숫자들 중 두 개를 더한 값이 탐색하는 숫자가 될 수 있는지 확인한다.
   1. start_idx를 0, end_idx를 N-1로 초기화한다.
   2. start_idx < end_idx 조건을 만족하는 동안 아래 과정을 반복한다.
   3. 두 숫자에 자기자신이 포함되는 것을 방지하기 위해, start_idx가 현재 숫자 위치와 같다면 1을 더해주고, end_idx가 현재 숫자 위치와 같다면 1을 빼준다.
   4. numbers[start_idx] + numbers[end_idx]가 현재 숫자보다 크다면, end_idx에 1을 빼준다.
   5. numbers[start_idx] + numbers[end_idx]가 현재 숫자보다 작다면, start_idx에 1을 더해준다.
   6. numbers[start_idx] + numbers[end_idx]가 현재 숫자와 일치한다면 탐색을 종료하고 count에 1을 더한다.
5. count를 출력한다. 

 

📌시도 회차 수정사항

1회차

투포인터와 이분탐색을 헷갈려서 코드를 잘못 설계했다.

2회차

문제에서 수의 범위가 양수에 한정된 줄 알고 수의 탐색 범위를 세번째 숫자부터로 지정했고, start_idx를 0, end_idx를 현재 숫자 위치-1로 설정했다. 이 부분을 수정해서 정답을 받았다.

 

📌정답 코드

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

count = 0
for i in range(N):
    cur_num = numbers[i]
    start_idx = 0
    end_idx = N - 1
    
    while start_idx < end_idx:
        if start_idx == i:
            start_idx += 1
            continue
        if end_idx == i:
            end_idx -= 1
            continue
        
        sum_val = numbers[start_idx] + numbers[end_idx]
        if sum_val == cur_num:
            count += 1
            break
        elif sum_val > cur_num:
            end_idx -= 1
        else:
            start_idx += 1
    
print(count)