자료구조 - 투 포인터

투 포인터란, 두 개의 포인터가 간격을 좁히거나 넓혀가면서 연산 결과가 조건을 만족하는지 알아내는 알고리즘을 의미합니다. 투 포인터 알고리즘은 크게 두 가지 종류로 구분될 수 있습니다.

• 투 포인터 내의 구간에 속한 모든 값을 선택하는 경우
• 투 포인터가 가리키는 두 값만 선택하는 경우

또한, 일반적으로 정렬과 함께 사용되는 경우가 많습니다. 그러면 지금부터 투 포인터 알고리즘을 이용하여, 문제를 풀어보도록 하겠습니다.

1. 연속된 자연수의 합 구하기

>> 백준 2018번 / 실버 5

1) Problem

2) Test Case

3) Solution

num = int(input())

count = 0 
start_index = 1 # index를 1부터 시작하여 원소와 index를 일치시킴
end_index = 1
sum = 1 

while end_index <= num:
    if sum == num:
        count += 1
        end_index += 1
        sum += end_index
    elif sum > num:
        sum -= start_index
        start_index += 1
    else :
        end_index += 1
        sum += end_index
print(count)

① num

• 입력된 자연수

② count

• 주어진 조건을 만족하는 경우의 수

③ sum

• start_index와 end_index가 모두 1로 초기화되므로, sum도 1로 초기화해야 한다.

④ while

• sum과 입력된 자연수가 같은 경우
  • count를 1 올린다.
  • end_index를 1 증가시킨 후 sum에 end_index의 원소를 더해주어야 한다.
  • 반대로 sum에서 start_index의 원소를 빼고 start_index를 1 증가시키는 방법도 가능하다.
  • 단, start_index의 경우 원소를 먼저 뺀 후에 index를 증가시켜야하고, end_index의 경우 index를 먼저 증가시키고 원소를 빼야한다.
• sum이 입력된 자연수보다 큰 경우
  • start_index의 원소를 빼고 start_index를 1 증가시킨다.
• sum이 입력된 자연수보다 작은 경우
  • end_index를 1 증가시킨 후 sum에 end_index의 원소를 더한다.

2. 주몽의 명령

>> 백준 1940번 / 실버 4

1) Problem

2) Test Case

3) Solution

import sys
input = sys.stdin.readline

size = int(input()) # 재료의 개수
target_num = int(input()) # 갑옷이 완성되는 번호의 합
material_list = list(map(int, input().split())) # 재료

material_list.sort()
count = 0

i = 0
j = size - 1

while i < j:
    if material_list[i] + material_list[j] < target_num:
        i += 1
    elif material_list[i] + material_list[j] > target_num:
        j -= 1
    else:
        count += 1
        i += 1
        j -= 1

print(count)

• while 조건을 i != j로 쓰지 않도록 주의한다.
• 위 조건에선, i와 j가 1 차이날 때 target_num과 일치할 경우, 무한 루프에 빠져 ArrayIndexOutOfBounds 에러가 발생한다.

3. 좋은 수 구하기

>> 백준 1253번 / 골드 4

1) Problem

2) Test Case

3) Solution

import sys
input = sys.stdin.readline

size = int(input())
num_list = list(map(int, input().split()))
num_list.sort()
count = 0

for k in range(size):
    target_num = num_list[k] # 좋은 수 여부를 확인하려는 값
    i = 0
    j = size - 1
    while i < j:
        if num_list[i] + num_list[j] == target_num:
            if i != k and j != k: # 좋은 수를 구성할 때 자기 자신을 포함해선 안됨
                count += 1
                break # 좋은 수인지 확인만 하면 되고, 좋은 수를 구성하는 경우의 수는 필요하지 않음
            elif i == k:
                i += 1 # i가 k를 넘어가게 한 후 연산 재개
            elif j == k:
                j -= 1 # j가 k를 넘어가게 한 후 연산 재개
        elif num_list[i] + num_list[j] < target_num: # 일치하지 않을 때는 i, j가 k와 같은지에 관심 없음
            i += 1
        else:
            j -= 1
            
print(count)