[백준] 1306 달려라 홍준 java 쉬운 풀이 (그림으로 설명^^)

1. 문제 설명 📌

문제 링크

일반적인 슬라이딩 윈도우에서 구간 내 최대값을 반환하라는 조건이 추가되었다.

2. 접근 방식 🗃️

KEY WORD: Sliding Window, Data Structure(Deque)

(1) 코드 구현 순서

1. 슬라이딩 윈도우를 deque로 구현한다.
   • 내림차순 정렬 (최대값 = peek())
   • 슬라이딩 윈도우에서 빠져나가는 값은 deque에서도 똑같이 제거
   • rear > 신규값: 신규값을 deque에 추가한다.
   • rear < 신규값: rear를 poll 한다. (이는 rear > 신규값이 될 때까지 반복)
2. 0~2M-1에 해당하는 값들에 대해 먼저 슬라이딩 윈도우를 진행한다.
3. M ~ N-M까지 슬라이딩 윈도우를 진행한다. 진행하며, 당시 최대값을 StringBuilder에 추가한다.

(2) 해설

해당 문제는 i라는 임의의 값을 기준으로 i-(M-1) ~ i+(M+1)까지의 값들중 최대값을 찾아야 하는 문제이다. 시작점을 기준으로 하는 일반적인 슬라이딩 윈도우와 달리, 초기값 계산을 먼저 진행해야 한다.

과정 1번 슬라이딩 윈도우 구현 :hammer:

먼저 슬라이딩 윈도우는 현 구간의 값들 중 유효한 값들이 내림차순으로 정렬되어 있다. 여기서 유효한이란 조건을 추가한 이유는, 어떤 경우에도 최대값이 될 수 없는 수들은 deque에서 제외하기 때문이다.
예를 들어 윈도우에 새로 추가될 값을 A라고 해보자. deque는 내림차순이니, deque에서 제일 작은 값이 deque의 rear에 위치하게 될 것이다. 만약 rear < A라면, rear는 이후에 자기가 속하는 윈도우 구간 전체에 통틀어 최대값이 될 수가 없다. 왜냐하면, rear가 슬라이딩 윈도우 내에서 나올때까지 붙어다니는 후임자 A가 항상 rear보다 크기 때문이다. 따라서 rear의 값을 poll한다.
반대로, rear > A라면, rear가 윈도우에서 나가는 순간, A가 최대값이 될 가능성이 있기에 deque에 넣어두는 것이다. 

가령 다음과 같다고 할 때, 슬라이딩 윈도우를 한 칸 전진시키겠다.

2는 3 때문에 윈도우에 살아있는 경우 동안 절대 최대값이 될 수 없다.

Deque가 Value를 기준으로 정렬되어 있는데, 어떻게 구간에 없는 값을 제거할 수 있나요? :thinking:

Deque의 peek()은 구간내의 최좌단 이거나 그거보다 index가 큰 값임이 보장되어 있기 때문에 그렇다. deque가 가득찰 수 있는 경우는 매번 들어오는 신규값이 rear보다 작아서 삭제없이 추가만 이루어지는 경우이다. 이때, deque의 peek()은 항상 슬라이딩 윈도우의 최좌단이 되는 것이다. 따라서 우리는 deque.peek() < i - M 인지만 검사해서 없애면 된다.

과정 2 슬라이딩 윈도우 초기 세팅

슬라이딩 윈도우의 기준점이 시작점인 보통의 문제(ex- i ~ i+m까지로 구간 설정)와 달리 이번 문제는 현재 값 i를 기준으로 i-m ~ i+m의 값을 윈도우의 구간으로 설정하고 있다. 나는 가독성을 위해서 먼저 1 ~ 2M-1까지의 값을 deque에 정렬 시켜두고 시작했다.

예외처리

해당 문제에서는 2M-1(윈도우의 구간) < N이란 보장이 없다. 따라서 윈도우의 구간이 전체 숫자 길이를 넘을 경우, 그저 전체에서 최대값을 하나만 출력하는 것으로 예외처리를 해줘야 한다.

3. 코드 소개 🔎

import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    /*
    * 1. ArrayDeque로 슬라이딩 윈도우를 구현
    * 2. 해당 윈도우안의 값은 내림차순으로 정렬, 즉 deque의 front는 최대값을 유지
    * 3. deque의 front가 슬라이딩 윈도우 구간을 벗어나는지 확인 후 조치
    * 4. 신규값과 deque의 rear를 비교
    *   - rear > 신규 : 신규 값 deque에 추가
    *   - rear < 신규 : rear를 poll() (반복)
    * 5. 매 슬라이딩 윈도우 움직임마다, deque의 front를 출력
    * */

    public static void main(String[] args) throws IOException {
        // 변수 목록
        StringBuilder ans = new StringBuilder();
        int N, M;
        int [] ad;
        int MAX_SIGHT;
        ArrayDeque<Num> sight = new ArrayDeque<>();
        // 입력 받기
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ad = new int [N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            ad[i] = Integer.parseInt(st.nextToken());
        }
        MAX_SIGHT = Math.min(2*M-1, N);
        // 술라이딩 윈도우 초기 세팅
        for (int i = 0; i < MAX_SIGHT; i++) {
            if(sight.isEmpty()) sight.add(new Num(i, ad[i]));
            else {
                while (!sight.isEmpty()&& sight.peekLast().v < ad[i]){
                    sight.pollLast();
                }
                sight.add(new Num(i, ad[i]));
            }
        }
        ans.append(sight.peek().v).append(" ");
        // 예외 처리
        if(MAX_SIGHT != 2*M-1) {
            System.out.println(ans);
            return;
        }
        // 계산
        for (int i = M; i <= N-M; i++) {
            if(!sight.isEmpty()&&sight.peek().i <= i-(M)) sight.poll();
            while (!sight.isEmpty()&& sight.peekLast().v < ad[i+(M-1)]){
                sight.pollLast();
            }
            sight.add(new Num(i+(M-1),ad[i+(M-1)]));
//            System.out.printf("이번에 넣은 수의 index: %d, 이번에 넣은 수: %d\n",(i+(M-1)),ad[i+(M-1)]);
//            sight.forEach(o -> System.out.printf("%d번째, %d || ",o.i, o.v));
//            System.out.println("\n---------------------------------------");

            ans.append(sight.peek().v).append(" ");
        }


        System.out.println(ans);
    }
}

class Num {
    int i;
    int v;

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

코드가 헷갈리는 분들은 주석처리된 print문을 참고하며 이해하시길 바란다.

4. 배운 것들 🎯

나는 최소값 찾기를 복습하고자 비슷한 유형의 문제를 찾다가 이번 문제를 발견하여 풀게 되었다. 이번 문제를 T/C를 찾지 않고 풀어서, T/C를 생각해내는 능력을 기를 수 있었다. 이번 문제에서 T/C를 찾는 방법은

1. N과 M의 범위 유심히 보기
2. 값들을 다양한 경우의 수로 만들어 입력 넣어보기 (수가 점진적 증가 or 감소하는 경우, 같은 값만 쭉 있는 경우 등)