백준 21967번 - 세워라 반석 위에

Published on May 25, 2024

해당 포스팅에서는 백준 21967번 ‘세워라 반석 위에’ 문제를 통하여 투 포인트를 이용한 슬라이딩 윈도우 알고리즘에 대해서 살펴보고자 합니다.

1. 슬라이딩 윈도우 알고리즘이란?

특정 사이즈의 윈도우를 활용하여 배열의 일부를 확인하는 방법입니다. 해당 포스팅에서는 윈도우의 왼쪽과 오른쪽을 가리키는 두 개의 포인터를 활용하여 해당 문제를 풀어내는 방법에 대해서 알아보고자 합니다.

2. 21967번 접근 방법

문제 분석

수열의 길이와 수열을 초기에 제공해줍니다. 우리는 해당 수열에서 최댓값과 최솟값의 차이가 2를 초과하지 않는 수열의 최대 길이를 반환하면 됩니다.
여기서 중요한 지점은 수열의 길이가 최대 100만까지 주어질 수 있다는 것입니다.
즉, 재귀나 여러번 중첩된 반복문을 통하여 수열의 길이를 찾는 방법을 사용한다면 ‘시간 초과’가 발생합니다.

슬라이딩 윈도우 알고리즘 적용

따라서, 슬라이딩 윈도우 알고리즘을 사용하여 수열의 왼쪽 부분을 가리키는 left 포인터와 오른쪽을 가리키는 right 포인터를 이용하고자 합니다.
우선, 주어진 수열에서 right를 한 칸씩 이동시키며 최댓값과 최솟값의 차이가 2가 넘지 않는지 판별합니다.
만약, 2가 넘지 않는다면 right를 게속 전진시키고 차이가 2보다 크다면 left의 위치를 조정해야합니다.
left의 위치는 right와의 차이가 만약 2보다 크다면, 가장 큰 최솟값의 위치 + 1로 설정하여 시간 복잡도를 줄일 수 있습니다. 만약 right와의 차이가 2보다 작다면, 가장 큰 최댓값의 위치 + 1로 설정하면 됩니다.
Example 1: 주어진 수열이 (1 2 1 2 3 1 3 4) 라고 한다면, 4는 최솟값과 2이상 차이가 나기 때문에 left는 5 + 1인 6이 됩니다.
Example 2: 주어진 수열이 (4 5 4 3 5 4 1) 라고 한다면, 1은 최댓값과 2이상 차이가 나기 때문에 left는 4 + 1인 5부터 판별을 시작하면 됩니다.

3. 백준 21967번 문제

이제부터는 해당 문제를 통해 슬라이딩 윈도우 알고리즘이 어떻게 적용되는지 살펴보겠습니다.

Code (Java)

    public static int longestRockSequence(int[] A) {
       int N = A.length;
       int left = 0;
       int maxLen = 0;

       ##1
       int left_pointer_min = 0;
       int left_pointer_max = 0;

       for (int right=0; right < N; right++) {
           if (A[right] - A[left_pointer_min] > 2) {
               left = left_pointer_min + 1;

               ##2
               left_pointer_max = left;
               left_pointer_min = left;
               int tmp_pointer = left;
               for(;tmp_pointer<=right; tmp_pointer++){
                   if(A[tmp_pointer] <= A[left_pointer_min]){
                       left_pointer_min = tmp_pointer;
                   }
                   if(A[tmp_pointer] >= A[left_pointer_max]){
                       left_pointer_max = tmp_pointer;
                   }
               }

           } else if (A[left_pointer_max] - A[right] > 2) {
               left = left_pointer_max + 1;

               ##3
               left_pointer_max = left;
               left_pointer_min = left;
               int tmp_pointer = left;
               for(;tmp_pointer<=right; tmp_pointer++){
                   if(A[tmp_pointer] <= A[left_pointer_min]){
                       left_pointer_min = tmp_pointer;
                   }
                   if(A[tmp_pointer] >= A[left_pointer_max]){
                       left_pointer_max = tmp_pointer;
                   }
               }
           } else {
               ##4 
               if (A[left_pointer_max] <= A[right]) {
                   left_pointer_max = right;
               }
               if (A[left_pointer_min] >= A[right]) {
                   left_pointer_min = right;
               }
               maxLen = Math.max(maxLen, right - left + 1);
           }
       }
       return maxLen;
    }

Code analysis

코드 안에 ##으로 표기된 부분을 분석해보도록 하겠습니다.

1. Analysis

윈도우의 크기를 조절하기 위해 left index를 가리킬 Pointer를 2개 생성합니다.
이전에 설명한대로 설정된 윈도우 내에서 최댓값과 최솟값을 이용하여 left pointer를 변경해야하기 때문에 2가지 변수를 초기화합니다.

2. 3. Analysis

2번과 3번 부분은 동일한 코드로 작성되어 있습니다. 만약 주어진 조건을 위반하였을 경우, 경우에 따라 left는 left_pointer_max 혹은 left_pointer_min으로 업데이트 됩니다. 여기서 중요한 것은 left pointer가 업데이트 되었다면 새로 정의된 윈도우 범위 내에서 left_pointer_max와 left_pointer_min을 새로 업데이트 해야하기 때문에 작성된 부분입니다.
발생할 수 있는 문제점으로는 최악의 경우 N개의 배열 요소를 탐색하면서, 내부 포인터를 업데이트 해야하기 때문에 시간 복잡도가 O(N^2)이 될 수 있습니다.
또한, 해당 알고리즘의 문제 중 하나는 right를 이동시킬 때마다 A[right]에 대하여 판별을 진행하기 때문에 A[right]가 최댓값인지 최솟값인지를 모르는 상황입니다. 이로써 최대,최소 판별을 2번 진행해야 한다는 문제를 개선할 필요가 있어 보입니다.

4. Analysis

right pointer를 이동하면서 만약 left_pointer_max와 left_pointer_min이 업데이트될 수 있다면 계속 업데이트를 진행해주는 부분입니다.

Code (Java) - 개선

    public static int longestRockSequence(int[] A) {
       int N = A.length;
       int left = 0;
       int maxLen = 0;

       ##1
       Deque<Integer> minDeque = new LinkedList<>();
       Deque<Integer> maxDeque = new LinkedList<>();

       for (int right = 0; right < N; right++) {
           ##2
           while (!minDeque.isEmpty() && A[minDeque.getLast()] >= A[right]) {
               minDeque.pollLast();
           }
           while (!maxDeque.isEmpty() && A[maxDeque.getLast()] <= A[right]) {
               maxDeque.pollLast();
           }
           ##3
           minDeque.addLast(right);
           maxDeque.addLast(right);

           ##4
           while (A[maxDeque.getFirst()] - A[minDeque.getFirst()] > 2) {
               if (minDeque.getFirst() == left) {
                   minDeque.pollFirst();
               }
               if (maxDeque.getFirst() == left) {
                   maxDeque.pollFirst();
               }
               left++;
           }
           maxLen = Math.max(maxLen, right - left + 1);
       }
       return maxLen;
    }

Code analysis

이전 코드도 정상적으로 동작하지만, 중복된 부분을 개선하고 시간 복잡도를 줄이기 위해 다시 작성한 코드입니다.
이전 코드는 윈도우 내의 최댓값과 최솟값을 가리키는 포인터를 각각 지정하고 새로운 포인터를 지정할 때 해당 포인터를 경우에 따라 사용하는 방법으로 코드를 작성하였습니다.
반면, 해당 코드에서는 Deque를 이용하여 시간복잡도를 줄여서 풀이해보고자 합니다.
** 개선된 알고리즘은 GPT에서 아이디어를 얻어 작성되었습니다.

1. Analysis

최댓값과 최솟값을 유지하는 Deque를 선언합니다. 해당 Deque는 맨 앞에 항상 윈도우의 최댓값과 최솟값을 가집니다. 따라서, 조건을 판별할 때 minDeque와 maxDeque의 맨 앞부분만 가져와서 비교하면 됩니다.

2. Analysis

새로 들어온 A[right]와 Deque의 last element를 비교하여 새로운 값이 Deque내에 어디에 위치할지 결정합니다. 해당 알고리즘에 의해 minDeque는 항상 오름차순, maxDeque는 항상 내림차순으로 유지됩니다.

3. Analysis

##2에서 Deque가 새로운 값 A[right]를 기준으로 정리되었으니 Deque에 추가해줍니다.

4. Analysis

슬라이딩 윈도우의 위치를 결정하는 부분으로 첫 요소의 차이가 2보다 크다면 (조건을 배반한다면) left를 하나씩 증가시키면서 윈도우의 크기를 결정합니다. 따라서 문제가 없다면 right를 오른쪽으로 이동시키면서 윈도우의 크기를 증가시키고 문제가 확인된다면 left를 한칸씩 이동하면서 윈도우의 크기를 감소시키는 방식으로 동작합니다.

4. 마무리

슬라이딩 윈도우 방식을 통해 특정 조건을 만족하는 수열의 길이를 찾아내는 알고리즘에 대해서 알아보았습니다. 해당 문제를 풀 때, 중요한 부분은 left와 right를 가리키는 포인터를 사용한다는 것과 조건에 맞춰서 left 포인터를 이동시키는 것 그리고 시간 복잡도를 줄이는 방향으로 코드를 개선해야 한다는 것입니다.

참고 : 백준 21967번 - ‘세워라 반석 위에’