[Do-it! 코딩 테스트-기초편] 007. 주몽의 명령

문제

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

1940번: 주몽

---

접근

데이터 크기: 15,000

시간 제한: 2초

 

재료를 2개 골라 합했을 때 갑옷이 완성되는 번호와 같다면 개수 증가

갑옷을 완성시킬 재료 2개를 고르려면 투 포인터를 사용하는 것이 좋겠다.

투 포인터와 정렬.

 

일반적인 정렬은 O(NlogN)의 시간 복잡도를 가진다.

데이터의 크기가 15,000이기 때문에 정렬은 문제 없다.

하지만 이중 for문을 사용한다면 시간 복잡도가 O(N^2) 이상이다.

2초로는 부족하기 때문에 이중 반복문말고 투 포인터를 사용해야한다.

---

코드

import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

num = list(map(int, sys.stdin.readline().split(' ')))  # 중복 x
num.sort()

start = 0
end = N - 1
count = 0
# 2개를 합해서 M이 되는 개수

# 2 7 4 1 5 3
# 1 2 3 4 5 7

while start != end:
    if num[start] + num[end] == M:
        count += 1

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

print(count)

---

설명

재료 고유 번호는 중복이 없다. 파이썬 내장 함수인 sort()를 사용하여 입력받은 리스트를 정렬한다.

오름차순 정렬된 리스트는 양쪽 끝에서 부터 포인터를 이동하며 합이 M인 순간을 찾는다.

 

포인터 이동 조건은 다음과 같다:

두 값의 합이 M보다 작으면 -> 두 값의 합을 키우는 쪽으로 포인터를 이동 -> start += 1

두 값이 합이 M보다 크면 -> 두 값의 합을 낮추는 쪽으로 포인터를 이동 -> end -= 1

 

왼쪽 포인터인 start를 증가시키면 오름차순인 리스트에서 더 큰 값을 가리키게 되니까 합이 커짐.

반대도 마찬가지

 

두 값의 합이 M인 순간에 count를 증가시켜 갑옷 완성 가능 개수를 얻었다.

---

알고리즘

투 포인터