19. 투 포인터, 슬라이딩 윈도우 (2)

앞서 투 포인터의 개념에 대해 설명을 하였습니다. 이번에는 슬라이딩 윈도우에 대해 설명해보도록 하겠습니다. 

때에 따라서 투 포인터와 슬라이딩 윈도우를 구분없이 이야기하거나 개념이 혼동되는 경우가 꽤 있을 정도로 둘은 유사한 접근 방식을 갖고 있는 알고리즘입니다. 투 포인터는 앞에서 언급한 대로 연속적인 데이터가 주어졌을 때 두 개의 포인터를 이용하여 범위를 정해주고 그 범위에 포함된 데이터의 합 등 연산을 한뒤 그것이 원하는 값인지 검증을 하고 조건에 맞지 않는다면 조건에 맞출 수 있도록 end pointer나 start pointer를 적절하게 이동시켜주면서 모든 데이터를 확인하는 방식의 알고리즘이었습니다. 

슬라이딩 윈도우는 투 포인터와 유사하게 접근하되 투 포인터처럼 범위의 크기가 줄었다 늘었다 하는 것이 아니라 일정한 크기를 유지하면서 이동한다는 점에서 차이가 있습니다. 그렇기 때문에 투 포인터처럼 데이터의 크기와 데이터 값이 주어지는 동시에 특정 범위가 주어지고 그 범위 내에서 연산처리가 이루어지도록 요구하고 있다면 이는 슬라이딩 윈도우 문제로 볼 수 있습니다.

그러면 이를 효율적으로 처리할 수 있는 방법은 무엇일까요.

실제로 어떤 식으로 알고리즘이 작동하는지 아래의 예시를 통해 살펴보겠습니다.

숫자 N개와 범위 L이 주어지고, 인덱스 i가 0에서부터 N까지 증가할 때 i - L + 1에서 i까지의 인덱스 내에 있는 수들 중에서 가장 작은 수를 찾아 출력해주는 문제가 있다고 해보겠습니다. 아래는 N = 12, L = 3인 경우의 예시입니다. 인덱스가 0과 1인 경우 시작점이 음수가 되어 문제의 범위를 벗어나게 되는데 이경우는 벗어나는 부분을 제외한 범위 내에서 가장 작은 수를 찾아주는 문제로 이해하고 풀면 됩니다.

0	1	2	3	4	5	6	7	8	9	10	11
1	5	2	3	6	2	3	7	3	5	2	6

일단 이 문제를 풀기에 앞서 리스트 하나를 준비합니다. 리스트에는 문제의 답이 될 수 있는 수들의 인덱스를 저장해둘 것입니다. 리스트는 인덱스를 키워가면서 답이 될 가능성이 없는 수들의 인덱스를 리스트에서 제거해 나갑니다. 또한 인덱스가 커지면서 범위에서 벗어나 더이상 답이 될 수 없는 경우에도 리스트에서 제거할 것입니다.

위와 같이 수들이 주어진 경우 i가 0인 경우, 즉 범위에 다른 수들이 포함되어있지 않고 0에 해당하는 숫자 1만 범위에 들어온 경우라면 범위내 최소값은 1이라는 것을 알 수 있습니다. 범위 내 최소값을 파란색으로 표시하도록 하겠습니다.

[ 0 ]

그다음 인덱스 1번째의 값 5부터는 이 값이 기존의 최소값을 대체할 수 있는지를 확인하는 작업이 필요합니다. 만일 5가 기존 리스트에 들어있는 값들보다 작은 값이라면 앞으로 최소값을 출력할 때는 기존값들을 대체하여 5가 출력되어야 할 것입니다. 하지만 5는 1보다 크기 때문에 1을 대체할 수 없으므로 1은 여전히 리스트 내에 존재하게 됩니다.

[ 0, 1 ]

그다음 인덱스 2번째의 값 2를 확인하게 되면 2가 5를 대체할 수 있다는 것을 알게 됩니다. 범위 내에 5보다 작은 2가 생겼고 이값이 범위에 들어온 이상 5는 최소값으로 사용되지 않을 것입니다. 그렇기 때문에 2보다 큰값은 이제 리스트에 남아 있을 이유가 없습니다. 리스트에서 순차적으로 5보다 큰 값을 제거해줍니다. 리스트는 아래와 같은 상태가 될 것입니다. 빨간색으로 표시된 부분은 실제로는 제거되어 리스트에 존재하지 않습니다.

[ 0, 1, 2 ]

그다음 인덱스 3인 경우, 최초로 범위에 포함되지 않아 리스트에서 제거되어야 하는 값이 생깁니다. 인덱스 0인 값은 범위 3에 포함되지 않기 때문에 리스트에 있을 수 없게 됩니다. 리스트에서 범위에서 벗어난 값들은 제거해주도록 합니다. 3은 2보다 크기 때문에 2는 리스트에 계속 포함될 수 있습니다. 그리고 지속적으로 범위 내에서 가장 작은 숫자에 해당하게 됩니다.

[ 0, 1, 2, 3 ]

이제 어떤 식으로 로직이 반복되는지 알 수 있기 때문에 인덱스 끝까지 반복하며 확인해줍니다. 반복적으로 작업을 해주다보면 우리가 원하는 최소값은 항상 리스트의 0번째에 존재한다는 것을 알 수 있습니다. 즉 범위에서 벗어났다면 제거되었을 것이고, 범위 내에 아직 존재한다면 자기보다 작은 값이 들어온 적이 없어 가장 작은 값인 상태가 유지되기 때문입니다. 그렇기 때문에 우리가 원하는 범위 내에서 가장 작은 값은 인덱스를 늘려서 위의 단계를 처리하고 매번 리스트의 0번째 값을 가져와서 저장해주면 되는 것입니다.

코드로 확인해보면 아래와 같습니다.

11003번: 최솟값 찾기

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

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.ArrayDeque;

import java.util.Deque;

import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        Deque<Integer> deque = new ArrayDeque<>();

        st = new StringTokenizer(br.readLine().trim());

        int N = Integer.parseInt(st.nextToken());

        int L = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine().trim());

        int[] A = new int[N];

        for (int i = 0; i < N; i++) {

            A[i] = Integer.parseInt(st.nextToken());

        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {

            while (!deque.isEmpty() && deque.peekFirst() <= i - L) {

                deque.pollFirst();

            }

            while (!deque.isEmpty() && A[deque.peekLast()] > A[i]) {

                deque.pollLast();

            }

            deque.add(i);

            sb.append(A[deque.peekFirst()]);

            sb.append(' ');

        }

        System.out.println(sb.toString());

    }

}