[백준] 1940번 주몽

 

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

1940번: 주몽

풀이

2개의 숫자를 더해 특정 숫자 M이 나오는지 확인하는 문제이다. N은 최대 15000이고
모든 경우의 수를 구하게 되면 15000 * 15000 / 2 정도가 나오기 때문에 시간 초과가 발생하게된다.

즉 더욱 단순하게 풀 수 있어야 하는데 이런 경우에는 투 포인터를 이용하여 양쪽에서 검사하면 쉽게 풀 수 있다.
입력 받은 숫자를 정렬한 뒤 양쪽에서 확인하면 현재 숫자가 M보다 큰지 작은지 판단하기 쉽다.

오름차순으로 정렬했다고 가정했을 때 
1, ....., N 으로 정렬된 숫자에서
1번째 + N번째 숫자가 M보다 크다면 N을 가리키고 있는 포인터를 한칸 앞으로 당기면 N - 1 번째 숫자는 항상 N보다 작기 때문에 합의 크기를 줄일 수 있다.
반대로 1번째 + N번째 숫자가 M보다 작다면 1을 가리키고 있는 포인터를 한칸 뒤로 밀면 2번째 숫자는 항상 1번째 숫자보다 크기 때문에 합의 크기를 키울 수 있다.

이 방법을 이용하여 구하면 총 탐색 횟수는 숫자의 길이 N만큼이 된다.

 

data = list(map(int, input().split()))

data.sort(reverse=True)
start = 0
end = N-1 #len(data)

먼저 입력받은 데이터를 정렬하고 투 포인터의 시작, 끝 지점을 지정한다.

 

while True:
    if end <= start:
        break

    if data[start] + data[end] == M:
        answer += 1
        start += 1
        end -= 1
    elif data[start] + data[end] > M:
        start += 1
    elif data[start] + data[end] < M:
        end -= 1

print(answer)

종료 조건은 뒤쪽 포인터와 앞쪽 포인터가 동일한 곳을 선택하거나, 교차되는 순간이다.(모든 숫자 탐색 완료)

앞에 언급한대로 M을 만족하는 경우는 양쪽 포인터 이동
M보다 작은 경우는 앞쪽 포인터 이동
M보다 큰 경우는 뒤쪽 포인터를 이동하는 것으로 탐색을 수행했다.

 

 

전체 코드

N = int(input())
M = int(input())

data = list(map(int, input().split()))

data.sort(reverse=True)
start = 0
end = N-1 #len(data)
answer = 0

while True:
    if end <= start:
        break

    if data[start] + data[end] == M:
        answer += 1
        start += 1
        end -= 1
    elif data[start] + data[end] > M:
        start += 1
    elif data[start] + data[end] < M:
        end -= 1

print(answer)

투 포인터를 활용하면 구현 방법도 시간도 줄일 수 있는 문제이다.
자주 투포인터 문제를 풀어보는 것으로 문제를 만났을 때 생각을 하는 것이 중요할 것 같다.