[알고리즘] 투 포인터

투 포인터

간단 정리

 

두 개의 포인터를 사용하여 풀이한다.

하나의 배열에서 풀이하는 문제와 두 개의 배열에서 풀이하는 문제가 있다.

핵심은 포인터를 어떤 조건에서 움직일 것인가를 명확히 하는 것이다.

 

두 개의 포인터와 조건을 다 따로 보려고 하면 분기점이 많아지므로

오른쪽 포인터를 고정시키는 테크닉과 오른쪽으로만 이동할 수 있는 설계가 필요하다.

 

 

---

 

 

예제

 

겹치는 건 싫어

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

20922번: 겹치는 건 싫어

import sys

def get_answer(N, K, numbers):
    records = [0] * 100001
    max_partial_length = 0
    left_idx = 0

    for right_idx in range(N):
        num = numbers[right_idx]
        if records[num] == K:
            max_partial_length = max(max_partial_length, right_idx - left_idx)
            while numbers[left_idx] != numbers[right_idx]:
                records[numbers[left_idx]] -= 1
                left_idx += 1
            left_idx += 1
            records[num] -= 1
        records[num] += 1

    max_partial_length = max(max_partial_length, N - left_idx)
    return max_partial_length

def sol():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    numbers = list(map(int, input().split()))
    answer = get_answer(N, K, numbers)
    print(answer)

 

 

 

---

 

 

표절

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

2428번: 표절

 

import sys


input = lambda: sys.stdin.readline().rstrip()
N = int(input())
files = [*map(int, input().split())]

files.sort()

answer = 0
p1 = 0
for p2 in range(N):
    cut_off = files[p2] * 0.9
    while p1 < N and cut_off > files[p1]:
        p1 += 1
    answer += p2 - p1

print(answer)

 

 

---

 

두 큐 합 같게 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/118667

프로그래머스

 

def solution(queue1, queue2):
    length = len(queue1)
    window_length = length*2
    pointer = length-1
    s1, s2 = sum(queue1), sum(queue2)
    
    answer = 0
    q = queue1 + queue2 + queue1 + queue2
    for i in range(window_length):
        while pointer < window_length+i and s1 < s2:
            pointer += 1
            answer += 1
            
            s1 += q[i+pointer]
            s2 -= q[i+pointer]
        
        if s1 == s2:
            return answer
        
        s2 += q[i+window_length]
        s1 -= q[i]
        pointer -= 1
        answer += 1
    
    return -1

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int[] queue1, int[] queue2) {
        int length = queue1.length;
        int totalLength = length * 2;
        
        Queue<Integer> q1 = new LinkedList<Integer>();
        Queue<Integer> q2 = new LinkedList<Integer>();
        
        long sum1 = 0, sum2 = 0;
        for (int i=0; i<length; i++) {
            q1.add(queue1[i]);
            q2.add(queue2[i]);
            
            sum1 += queue1[i];
            sum2 += queue2[i];
        }
        
        int answer = 0;
        int maxAnswer = totalLength * 2;
        while (answer < maxAnswer) {
            if (sum1 < sum2) {
                sum1 += q2.peek();
                sum2 -= q2.peek();
                
                q1.add(q2.poll());
                
                answer++;
            } else if (sum1 > sum2) {
                sum1 -= q1.peek();
                sum2 += q1.peek();
                
                q2.add(q1.poll());
                
                answer++;
            } else {
                return answer;
            }
        }
        
        return -1;
    }
}

위 세 문제는 모두 동일한 로직으로 구현했다.

오른쪽 포인터를 고정시키고 왼쪽 포인터를 움직일 수 있도록 조건을 구현하는 방법이다.

 

 

---

 

 

회전초밥

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

15961번: 회전 초밥

import sys


input = lambda: sys.stdin.readline().rstrip()
N, d, k, c = map(int, input().split())
foods = [int(input()) for _ in range(N)]
window_size = len(foods)
foods += foods

unique = 0
eaten = [0] * (d+1)
for i in range(k):
    curr = foods[i]
    if not eaten[curr]:
        unique += 1
    eaten[curr] += 1
max_value = unique
if not eaten[c]:
    max_value += 1

for i in range(window_size):
    left = foods[i]
    eaten[left] -= 1
    if not eaten[left]:
        unique -= 1

    right = foods[i + k]
    if not eaten[right]:
        unique += 1
    eaten[right] += 1

    if not eaten[c]:
        max_value = max(unique+1, max_value)
    else:
        max_value = max(unique, max_value)

print(max_value)

 

슬라이딩 윈도우를 사용했다.

구현이 간편한게, 첫 윈도우로 변수들을 초기화한 후에는 윈도우를 옮기며 왼쪽, 오른쪽 처리만 해주면 된다.

 

 

---

 

 

 

블로그

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

21921번: 블로그

 

import sys


def answering():
    if max_value:
        print(max_value)
        print(answer)
        return
    print("SAD")


input = lambda: sys.stdin.readline().rstrip()
N, X = map(int, input().split())
visits = list(map(int, input().split()))

answer = 1
curr_sum = sum(visits[:X])
max_value = curr_sum
for i in range(X, N):
    curr_sum += visits[i]
    curr_sum -= visits[i-X]

    if max_value < curr_sum:
        answer = 1
        max_value = curr_sum
    elif max_value == curr_sum:
        answer += 1

answering()

 

역시 똑같이 슬라이딩 윈도우를 사용했다.

투 포인터와 슬라이딩 윈도우는 정해진 구현법 그대로 서술하는 것이 바람직하다.