[정렬/탐색] 백준 3273 두 수의 합 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

3273번: 두 수의 합

 

 

 

2. 문제 풀이

 서로 다른 양수로 이루어진 수열에서 두 수를 뽑아 X가 되는 경우를 찾는 문제입니다.

 

1 2 4 6 7 8 10
s                e

  오름차순으로 정렬하고, 양 끝을 가리키는 포인터를 이용해서 X를 탐색합니다. start 포인터는 0번부터 시작해서 +1씩 증가하고, end 포인터는 n-1번부터 시작해서 -1씩 감소합니다.

 list[start] + list[end] 두 수를 더해서 x가 되는지 확인하고, x보다 작으면 start포인터를 1칸 증가시키고, x보다 크면 end포인터를 1칸 감소시킵니다.

 start와 end 포인터가 서로를 지나치면, 모든 수열을 탐색한 것이므로 종룔합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input())
numlist = list(map(int, input().split()))
x = int(input())

# 정렬
numlist.sort()

# x값 찾기
cnt = 0
start = 0
end = n-1

while start < end:
    num = numlist[start] + numlist[end]

    #x와 같은 경우
    if num == x:
        cnt += 1
        start += 1

    #x보다 작은 경우
    elif num < x:
        start += 1

    #x보다 큰 경우
    else:
        end -= 1

print(cnt)​

 위 방법대로 코드를 구현했습니다. 양 끝 포인터가 가리키는 두 수를 더해서, x와 같으면 cnt+1하고 start를 1칸 전진합니다. 대신 end를 한 칸 당겨도 무관합니다.