[Python] 백준 1940번 주몽

투 포인터를 활용한 문제

 

제한시간은 2초지만 N의 범위가 15,000까지기 때문에 O(nlogn)의 시간복잡도 내에 풀면 된다.

파이썬의 정렬 라이브러리인 sort를 이용할 수 있다. 파이썬의 정렬 라이브러리는 병합정렬 기반으로 O(nlogn)의 시간복잡도를 가진다.

 

정렬 후 맨 앞과 맨 끝 인덱스를 기준으로 비교를 시작한다.

둘의 합이 M이 됐다면 cnt++ 후 각 값을 1씩 옮긴다.

둘의 합이 M보다 작다면 시작 인덱스 i++를 한다.

둘의 합이 M보다 크다면 끝 인덱스 j--를 한다.

# 주몽
# 두 숫자를 합쳐 M이 되어야 한다. N개의 숫자와 M이 주어졌을 때 몇 개의 조합이 만들어지는지 구하시오.
# 첫째 줄에는 숫자의 개수N이 주어진다. 두 번재 줄에는 M이 주어진다. 세 번째 줄에는 N개의 숫자들이 공백을 가지고 주어진다.
# 개수를 출력하시오.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
num = list(map(int, input().split()))
num.sort()
cnt = 0
i = 0
j = n - 1

while i < j:
    if num[i] + num[j] == m:
        cnt += 1
        i += 1
        j -= 1
    elif num[i] + num[j] > m:
        j -= 1
    else:
        i += 1

print(cnt)