[백 준/구현] 1940: 주몽

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

1940번: 주몽

풀이

import sys
input = sys.stdin.readline
from itertools import combinations

N = int(input())
M = int(input())
num = list(map(int, input().split()))

result = 0
for i in combinations(num, 2):
	if sum(i) == M:
		result += 1
print(result)

처음에는 조합으로 풀면 되겠다고 생각했는데, 시간 초과가 발생해서 다른 방식으로 풀어야하나 고민 중 "투포인터 알고리즘"을 활용해야 한다는 사실을 알게되었다.

• Two pointers 알고리즘
  • list에 순차적으로 접근할 때, 2개의 pointer를 기록하면서 처리해나가는 알고리즘으로 이렇게 두 가지의 포인터를 사용하여 문자열이나 배열(or list)에서 원하는 값을 찾거나 반목문을 써야할 때 쓰기 좋은 방식.
  • 즉, 시작점과 끝점으로 접근해야 할 데이터의 범위를 먼저 잡고 시작하는 방식에 기반
  • 투 포인터는 주로 정렬된 대상을 대상으로 한다. (파이썬 알고리즘 인터뷰 - 박상길 에 의하면)
• Two pointer 방식
  1. 앞에서 시작하는 포인터와 끝에서 시작하는 포인터

N = int(input())
M = int(input())
num = list(map(int, input().split()))

#우선 정렬을 진행한다. 보통 투포인터 알고리즘은 정렬된 대상을 대상으로한다.
num.sort()
# start 의 index는 0, end의 index는 맨 마지막 index를 가리킨다
start = 0
end = len(num) - 1
count = 0

#start 와 end 의 합이 M과 같으면 count 1하고, 제외한다
#start의 index가 end의 index보다 작을때까지 반복한다
while start < end:
	result = num[start] + num[end]
	# 양 두 끝의 합이 M보다 크면 end를 한칸씩 내린다
	if result > M:
		end -= 1
	# 양 두 끝의 합이 M보다 작으면 start를 한칸씩 올린다
	elif result < M:
		start += 1
	else:
		count += 1
		start += 1
		end -= 1
print(count)

이렇게 그냥 기본 방식인 탐색(반복문)을 쓰다 보면 시간이 오래 걸리거나 시간 초과가 나는 경우가 있는데 투포인터 알고리즘을 사용하면 메모리와 시간 효율성을 높일 수 있다.