[백준] 2905 홍준이와 울타리 문제 풀이 java (그림으로 쉽게 설명 ^^)

1. 문제 설명 📌

문제 링크

문제 설명이 어려워서 부연 설명을 하겠다.
N개의 울타리와 너비가 X인 룰러가 있다. 울타리의 경우 너비는 1로 고정이고, 높이만 1차원 배열 형식으로 주어진다. 당신은 룰러를 활용하여 페인트를 칠할 것인데, 너비가 X임으로, X 너비 내의 울타리는 한 번에 칠하게 될 것이다. 여기서 중요한 조건은 다음과 같다.

 

(1) 룰러의 부분이 허공에 닿으면 안된다.

왼쪽과 같이 일련의 울타리가 주어진다면, 오른쪽 그림의 테두리 안 쪽만 롤러를 돌려 칠할 수 있다는 말이다. 즉 롤러 너비 X 내에 제일 작은 울타리가 색칠의 기준이 된다.

 

(2) 칠한데는 또 칠할 수 있다.

다음과 같이 롤러의 너비가 3일 때, 처음 맞딱뜨리는 구간에서는 최대로 칠할 수 있는 높이가 1일 것이다.

롤러를 한 칸 옮기면 어떨까? 2가 바로 롤러로 칠할 수 있는 최대 높이가 된다. 이때, 칠한 곳을 또 칠해도 된다는 것이다.

다음과 같은 2가지 조건을 참고하여, 칠해지지 않은 부분의 최소값과, 필요한 최소한의 롤러질 횟수를 구하면 된다.

2. 접근 방식 🗃️

KEY WORD: Sliding Window, Monotone Queue

원래라면, 큰 접근 방식 개요를 설명하고 세세하게 접근 했을텐데, 이번 문제는 사전에 알아야할 내용이 있어 먼저 그것에 대해 말하고 큰 개요를 설명하겠다.

(1) 사전 지식: 슬라이딩 단조 큐에 대해

Monotone Queue(단조 큐)란 큐안의 값이 오름차순 혹은 내림차순으로 꾸준히 유지되는 큐를 말한다. 이걸 활용해 슬라이딩 윈도우를 구현해야 한다.
이런 식으로 둘을 결합해 푸는 문제 유형이 꽤 되는데, 이 자료구조를 가리킬만한 용어가 없어서 필자는 슬라이딩 단조 큐라고 부른다. 해당 개념에 대한 자세한 설명은 밑의 링크를 참고하기 바란다.

 

 

https://dalcheonroadhead.tistory.com/570

슬라이딩 단조 큐, 그림으로 쉽게 이해하기

 

 

 

간단히 슬라이딩 단조 큐의 개념에 대해 설명하면 다음과 같다.

 

0. Deck으로 구현한다.
1. 슬라이딩 윈도우를 움직이며 받아야 하는 신규값은 무조건 deck의 꼬리로 집어 넣는다.
2. 1번 규칙을 지키면서 deck 안을 비내림차순 혹은 비오름차순으로 유지시켜야 한다.
3. 슬라이딩 윈도우가 지나간 값은 deck에서도 제거 한다.
4. 1번 규칙을 지키면서 2번 규칙을 지키려면, 큐의 꼬리값과 신규값 간의 대소관계 비교가 필요하다. 가령 단조큐 안을 오름 차순으로 유지시킬 의도라면

• queue.rear() > new 라면 new가 큐의 꼬리에 들어가면 오름차순이 되지 않으므로, queue의 rear를 제거한다.
  (이 과정을 rear <= new 가 될 때까지 반복한다.)
  
  
• queue.rear() <= new 라면 new가 큐의 꼬리에 들어가도 오름차순이 유지되므로 그대로 넣는다.

이게 왜 필요함? 🤔

가령 문제에서 슬라이딩 윈도우 안의 최소값 혹은 최대값을 구하라는 요구사항이 나올 경우 필요하다. 슬라이딩 윈도우를 쓰는 것이 완전 탐색의 비효율을 줄이고, 윈도우의 머리 값과 꼬리값만 갱신하며 시간복잡도를 줄이기 위함인데, 구간 내 최소 혹은 최대값을 구하기 위해 슬라이딩 윈도우를 완전탐색한다면 해당 기술을 쓰는 의미가 없다.

이 경우 슬라이딩 단조 큐를 활용해 현 구간 내의 최소 혹은 최대값을 남긴다면 원래 슬라이딩 윈도우와 똑같이 구간의 머리와 꼬리값만 갱신해 나가며 효율적으로 풀 수 있기 때문이다.

이번 문제에서는 롤러가 칠하려는 구간 내에서 울타리 중 최소 높이인 것을 구하기 위해 사용했다. 단조큐를 비내림차순으로 정렬한다면, 현 구간 내의 최소 높이가 무엇인지 알 수 있다. 이제 사전 지식을 공부 했으니, 문제를 본격적으로 풀어보겠다.

(2) 칠한 부분은 다시 칠할 수 있다는 조건은 어떻게 구현?

결론: 실제 구현은 색칠이 중복되지 않게 한다.
이를 테면, 현재 조회 중인 울타리가 중복 색칠될 것 같으면 그것은 칠하지 않고 그 이전 울타리들만 색칠

해당 문제에서 가장 문제가 되는 것은 한번 롤러로 칠했더라도 다음 구간에서 더 칠 할 수 있다면, 덧칠이 가능하는 점이다. 밑의 그림과 같이 말이다.

전체 울타리 너비 - 색칠한 부분으로 문제를 풀려던 입장에서 이러한 중복된 색칠은 계산을 복잡하게 만든다. 그래서 구글링 하며 찾아낸 방법은 덧칠하기 직전까지만 칠하고 다음 구간으로 넘어가는 것이다. 이러면 중복이 없다. 그렇다면 다음 구간에서 덧칠이 될지 안될지를 어떻게 판단할 것인가? 방법은 다음과 같다.

 

"구간을 옮겼을 때, 구간 내 최소값이 변하면, 바뀐 구간부터는 어짜피 새로운 최소 높이로 다시 칠해야하므로 칠하지 않는다."

 

달리 말하면, "구간을 옮겼을 떄, 구간 내 최소값이 변하면, 이전 칠하지 않은 부분의 시작점 ~ 현 구간 직전까지 이전 최소 높이로 칠한다." 라는 말이 된다. 말로 하면 헷갈리니 그림으로 설명하겠다.

다음과 같은 예제가 존재한다고 할 때, 최초 구간의 칠할 수 있는 높이는 5일 것이다.

색으로 슬라이딩 윈도우는 표시 했지만 아직 칠하진 않았다! 왜냐하면 구간의 최소높이가 바뀌는 순간에 한 번에 칠해버리면 되기 때문이다. 일단 다음 구간으로 넘어가자.

아직 5가 최소 높이이다. 또 다음 구간으로 넘어가자.

이제 최소 높이가 6이 되었다! 최소 높이가 바뀌었음으로, 이후 부터는 6으로 다시 칠해야한다. 우리는 중복을 피하기 위해 index = 2 인 부분은 칠하지 않고, 이전의 칠하지 않은 부분인 0부터 1까지를 이전 최소 높이인 5로 칠하면 된다.

슬라이딩 윈도우는 계속 진행해보자. 다음 구간으로 갔더니 이번엔 바로 높이가 4로 바뀌었다. 이러면 아직 칠하지 않은 시작점인 index = 2부터 최소 높이가 바뀌기 직전 index = 4까지 6으로 칠하면 된다.

이런식으로 윈도우를 계속 움직이면, 다음 그림과 같이 최대한 칠할 수 있다.

그럼 이제 다음과 같은 궁금증이 생길 것이다.

(3) 구간의 최소 높이가 바뀌는 시점은 언제일까?

2가지 순간이 있다.

 

• (a) 슬라이딩 윈도우를 옮겼을 때, 신규 삽입값이 최소값이 되는 경우 (최소값이 작아짐)
• (b) 슬라이딩 윈도우를 옮겼을 때, 최좌단 값이 삭제되어 2번째로 작았던 값이 최소갑이 되는 경우 (최소값이 커짐)

위의 예시에서 첫번째 색칠하던 순간이 b에 해당하고, 두 번째 색칠하던 순간이 a에 해당한다. 위와 같은 순간이 오면 (이전에 색칠하지 않은 부분의 길이) * (이전 최소 높이) 로 색칠한 부분을 구하면 된다.

(4) 롤질한 횟수 구하기

최소 높이가 X너비 이상 같은 경우 어떤가?

다음과 같은 경우, index = 5의 4를 만나 0에서 4까지 울타리가 높이 3으로 칠해질 것이다. 룰러의 너비가 3임으로 2번 칠하게 될 것이다. 이처럼 최소 높이가 같은 구간이 0에서 X의 길이일 때는 롤질 1번, X+1 ~ 2X의 길이일 때는 롤질 2번 ... 이런 식으로 규칙성이 생길 것이다. 따라서 색칠해야하는 구간의 길이를 N으로 나누었을 때 몫 + 1로 하면 계산이 편할 것이다. 계산 식으로 하면

\[ \frac{색칠해야 하는 길이 - 1}{N} + 1\]

이다.

어? 근데 왜 색칠해야 하는 길이에 -1을 해줄까? 🧐

나눗셈이 딱 맞아떨어지는 순간 또한 제대로 계산하기 위해서 이다. 만약 칠해야하는 부분의 길이가 X라면 롤질을 한 번만 하면 되지만, 나눗셈 + 1로 계산 시에는 2번으로 된다. 이를 방지하기 위해, 분자에 -1을 해주어 나누어 떨어지는 경우도 일부러 나누어 떨어지지 않게 만든다.

(5) 예외 처리: 모든 울타리 높이가 같을 때

우리는 최소높이가 바뀌는 시점을 기준으로 코드를 짰음으로 모든 울타리 높이가 같을 경우를 예외처리 해줘야 한다. 높이 배열의 맨 끝에 0을 하나 추가한다. 이러면, 맨 마지막에는 무조건 0을 만나서 그 전까지 안 칠해진 부분을 전부 마지막 높이로 칠해주기 때문이다.

(6) 코드의 큰 흐름

1. 슬라이딩 윈도우를 단조 큐로 구현 후 맨 처음 구간의 값에 대한 계산을 한다. (초기 세팅)
   (해당 부분을 미리 계산해야 다음부터 한 칸씩 움직이는 계산을 할 수 있다.)
2. 최초 구간의 최소 높이, 안 칠해진 부분의 시작점 변수, 롤질 횟수 변수, 전체 울타리 너비(누적합)를 구한다.
3. 슬라이딩 윈도우를 한 칸씩 움직인다.
   • 신규값을 삽입하고, 최소 높이가 바뀌었는지 체크한다. (바뀌었을 시, 색칠 안된 이전 구간의 길이 x 이전 최소 높이)
   • 최좌단 값을 삭제하고 최소 높이가 바뀌었는지 체크한다. (바뀌었을 시, 위와 같이 계산)

3. 코드 소개 🔎

import java.io.*;
import java.util.*;

public class Main {

    /*
    * b2905 홍준이와 울타리
    * 1. 슬라이딩 윈도우 초기값 세팅 (0~X 사이 최소값을 deque 맨 위로)
    *
    * 2. 슬라이딩 윈도우를 움직이며 신규 값 삽입으로 구간 내 최소값이 갱신되었을 경우,
    *       이전 안 칠 한 곳부터 i-1(직전)위치까지 이전 최소 높이로 칠하기
    *
    * 3. 슬라이딩 윈도우를 움직이며, 최소값이 구간을 벗어나면서 최소값이 갱신되었을 경우,
    *       이전 안 칠 한 곳부터, 구간에 벗어난 해당 값까지 최소 높이로 칠하기
    *
    * 4. 최소높이가 구간을 여러번 움직임에도 갱신되지 않는 경우에 대한 예외처리
    *       (n=12, x=4, 3333 3333 3333) -> 갱신안된 길이/x + 1 = 롤러질 한 횟수
    * */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        int [] values = new int [N+1];
        ArrayDeque<Fence> adq = new ArrayDeque<>(); // 슬라이딩 윈도우 -> 현재 롤러가 움직일 구간
        long area = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            values[i] = Integer.parseInt(st.nextToken());
            area += values[i];
        }

        // 1. 초기 세팅 -> 슬라이딩 윈도우 구간내 값들 중 유효한 값을 오름차순으로 유지
        //                  (유효한 값 = 구간 내 최소높이가 될 가능성이 있는 값)
        for (int i = 0; i < X; i++) {
            Fence now = new Fence(i, values[i]);
            while (!adq.isEmpty() && adq.peekLast().v > now.v) adq.pollLast();
            adq.add(now);
        }
//        for(Fence temp : adq){
//            System.out.print(temp.v+" ");
//        }
//        System.out.println();

        // 2. 계산
        int recent_height = adq.peek().v;  // 마지막으로 울타리 칠한 후, 갱신한 큐 내 최소높이
        int roller_cnt = 0;     // 롤러질한 횟수
        int idx = 0;            // 마지막으로 울타리 칠한 후, 갱신한 안 칠한 부분의 시작점

        for (int i = X; i <= N; i++) {
//            System.out.printf("계산 전--AREA: %d, ROLLER_CNT: %d recent-height: %d, idx: %d --"
//                + "현재 index: %d\n",area,roller_cnt, recent_height, idx, i);
            Fence now = new Fence(i, values[i]);
            while (!adq.isEmpty() && adq.peekLast().v > now.v) adq.pollLast();
            adq.add(now);

//            for(Fence temp : adq){
//                System.out.print(temp.v+" ");
//            }
//            System.out.println();

            if(!adq.isEmpty() && adq.peek().v != recent_height){
                roller_cnt += (i-1-idx)/X + 1;
                area -= (long) (i - idx) *recent_height;
//                System.out.printf("(2)신규 값 삽입하며 최소값 갱신 -- 빠져 나가는 값: %d \n", (i-idx)*recent_height);
                recent_height = adq.peek().v;
                idx = i;

            }

            if(!adq.isEmpty() && adq.peek().i <= i-X){
                Fence past = adq.poll();
                if(!adq.isEmpty() && adq.peek().v != past.v){
                    roller_cnt += (past.i - idx)/X + 1;
                    area -= (long) (past.i - idx + 1) * recent_height;
//                    System.out.printf("(3)최좌단 삭제하며 최소값 갱신 -- 빠져 나가는 값: %d \n", (past.i - idx + 1)*recent_height);
                    recent_height = adq.peek().v;
                    idx = past.i + 1;
                }
            }
        }
        System.out.println(area);
        System.out.println(roller_cnt);
    }
}

class Fence {
    int i;
    int v;

    public Fence(int i, int v){
        this.i = i;
        this.v = v;
    }
}

코드를 보면 색칠이 안된 구간의 길이를 구할 때, 신규 값 삽입 시와 제일 오래된 값 삭제 시의 계산이 다르다.
신규 값 삽입으로 인해 최소값이 변경된 경우, 최소값이 단조큐의 front에 위치할 것이다. 우리는 시작점부터 해당 최소높이를 만나기 이전까지의 길이를 구하면 되므로, 최소값의 index인 i의 직전인 i-1까지의 길이를 계산하면 된다.

 

(주의!) 단조큐 내 최좌단 값 삭제 후 최소 높이가 달라져서 색칠 범위를 정할 때,
단조 큐의 front.index -1 을 칠하는 구간의 끝으로 선정하면 안되는 이유!

삭제 후 최소값이 변경된 경우, 최소 높이가 된 단조 큐의 front의 index가 색칠해야하는 범위의 직후 index라고 보장하기 어렵다.

해당 6,7,8 구간에 슬라이딩 윈도우가 존재한다면, 최소 높이는 4이다. 한칸 움직여보면,

최소 높이가 6이다. 하지만 6은 4의 바로 직후 index가 아님을 알 수 있다. 따라서 이전 최소높이의 index를 포함하여 색칠해야할 길이를 측정한다.

4. 배운 것들 🎯

"중복해서 색칠할 수 있다."라는 조건이 넘 어려워서 다른 사람의 풀이를 공부한 뒤 다시 스스로 문제를 풀어보았다. 해당 풀이 코드가 C++이라 내 것으로 내재화 하는데 시간이 좀 걸렸다. 다음은 내가 참고했던 감사한 블로그 들이다.

 

 

https://jaimemin.tistory.com/832

백준 2905번 홍준이와 울타리

 

 

 

https://mingmeng030.tistory.com/63

[백준][JAVA] 2905 : 홍준이와울타리