[python 기초] 백준: 1940번 / Two pointers

📍In a nutshell...

• Two pointers 알고리즘
  • list에 순차적으로 접근할 때, 2개의 pointer를 기록하면서 처리해나가는 알고리즘
  • 즉, 시작점과 끝점으로 접근해야 할 데이터의 범위를 먼저 잡고 시작하는 방식에 기반

문제)

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다.
갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M이 되면 갑옷이 만들어 지게 된다.

야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

풀이)

만약 two pointers 알고리즘을 모른다면, 아마 가장 먼저 떠오르는 방식은 for문을 돌리는 것이다.

#방법1 - for문 사용 

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


length = len(my_list)
cnt = 0

for i in range(0, length-1):
    for j in range(i+1, length):
        result = my_list[i] + my_list[j]
        if result != M: continue
        cnt += 1 

print(cnt)

하지만 위의 풀이는 for문이 이중으로 걸려, my_list의 개수가 늘어날수록 시간복잡도가 매우 높아진다. 그래서 위의 풀이대로 제출하면 시간초과로 fail.

이 때 two pointers 알고리즘을 사용하면 선형적으로 풀 수 있다.

#방법2 - two pointers

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

my_list.sort()
start, end = 0, len(my_list)-1
cnt = 0 

while start < end: 
    result = my_list[start] + my_list[end]
    if result > M:
        end -= 1 
    elif result < M:
        start += 1
    else:
        cnt   += 1 
        start += 1 
        end   -= 1 

print(cnt)

• 주어진 list를 먼저 정렬한다 (오름차순 혹은 내림차순, 현재는 오름차순으로 정렬함)
• start 의 index는 0, end의 index는 맨 마지막 index를 가리킨다
• start 와 end 의 합이 M과 같으면 count 1하고, 제외한다
  • 양 두 끝의 합이 M보다 크면 end를 한칸씩 내린다
  • 양 두 끝의 합이 M보다 작으면 start를 한칸씩 올린다
  • start의 index가 end의 index보다 작을때까지 반복한다

비슷한 문제로, N개의 자연수로 구성된 list에서 결과가 M인 부분 연속 수열을 구하는 문제도
two pointers 방식으로 풀 수 있다.

N = 5
M = 5
data = [1,2,3,2,5]

cnt = 0
part_sum = 0
end = 0

for start in range(n):
	#부분합이 m보다 작으면 계속 index를 높이면서 더해준다 
	while part_sum < M and end < n:
    	sum += data[end]
        end += 1
    
    #만약 m보다 크면 start index에 해당하는 숫자를 빼주고, 같으면 count 1 한다 
   	if part_sum == m: cnt += 1 
    part_sum -= data[start]
    
print(cnt)

문제 출처: 백준
추가 참고 영상: https://youtu.be/ttLRltNDiCo