달려라 홍준

류한선·2025년 6월 19일

실기연습-2

목록 보기

8/95

좋아! 백준 1306번 "달려라 홍준" 문제는 슬라이딩 윈도우(Sliding Window) 또는 우선순위 큐, 세그먼트 트리 등을 사용할 수 있는 문제야. 우선 문제의 핵심부터 정리하고 예제를 구성한 뒤, Java 코드 전체를 만들고 그 코드를 한 줄씩 매우 자세하게 해설할게.

🔍 문제 핵심 요약

홍준이는 조명이 설치된 N개의 칸을 따라 달린다.
각 칸에는 높이가 있음.
홍준이는 항상 연속된 2 * m - 1개의 칸이 비추는 조명 아래를 달려야 함.
그 조명 범위에서 가장 높은 조명을 본다 → "가장 높은 높이" 출력

즉, 길이 N의 배열에서 윈도우 크기 2*m - 1짜리 슬라이딩 윈도우를 이동시키면서, 윈도우 내 최댓값들을 출력하는 문제임.

📥 입력 예제 (내가 정함)

입력:
8 2
2 1 4 5 1 3 3 2

설명:
N = 8, M = 2 → 슬라이딩 윈도우 크기 = 2 * 2 - 1 = 3
배열: [2, 1, 4, 5, 1, 3, 3, 2]

윈도우 위치별 최대값:
[2, 1, 4] → 4  
[1, 4, 5] → 5  
[4, 5, 1] → 5  
[5, 1, 3] → 5  
[1, 3, 3] → 3  
[3, 3, 2] → 3

최종 출력: `4 5 5 5 3 3`

✅ Java 전체 코드 (Deque 이용 슬라이딩 윈도우 최댓값)

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

public class Main {
    public static void main(String[] args) throws IOException {
        // 입력을 위한 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 전체 칸 수
        int M = Integer.parseInt(st.nextToken()); // 비추는 범위 중앙 기준 거리

        int[] heights = new int[N]; // 높이 배열
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            heights[i] = Integer.parseInt(st.nextToken()); // 높이 입력 받기
        }

        int windowSize = 2 * M - 1; // 슬라이딩 윈도우 크기
        Deque<Integer> deque = new LinkedList<>(); // 인덱스를 저장할 덱

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            // 범위를 벗어난 인덱스 제거
            while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize) {
                deque.pollFirst();
            }

            // 덱의 뒷부분에서 자신보다 작거나 같은 높이 제거 (최댓값 유지)
            while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i]) {
                deque.pollLast();
            }

            deque.offerLast(i); // 현재 인덱스를 덱에 추가

            // 첫 윈도우의 끝 도달 이후부터 결과 출력
            if (i >= windowSize - 1) {
                sb.append(heights[deque.peekFirst()]).append(" ");
            }
        }

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

🔬 코드 라인별 상세 해설 + 예제 흐름 분석

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

표준 입력(System.in)을 빠르게 읽기 위한 객체 생성.
이유: Scanner보다 훨씬 빠름.

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

입력값 "8 2"을 공백 기준으로 나누기 위해 사용.

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

`int M = Integer.parseInt(st.nextToken());`

N = 8, M = 2 입력받음

`int[] heights = new int[N];`

높이 정보를 저장할 배열 선언 → heights = [2,1,4,5,1,3,3,2] (다음 줄에서 채워짐)

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

`for (int i = 0; i < N; i++) { heights[i] = Integer.parseInt(st.nextToken()); }`

높이 배열 입력: [2, 1, 4, 5, 1, 3, 3, 2] 생성됨.

`int windowSize = 2 * M - 1;`

슬라이딩 윈도우 크기 계산
M = 2 → 2*2 - 1 = 3칸씩 검사

`Deque<Integer> deque = new LinkedList<>();`

높이 배열의 인덱스를 저장하는 덱 사용
현재 윈도우 범위 내 최댓값의 인덱스를 유지하는 자료구조

`StringBuilder sb = new StringBuilder();`

결과값 출력 최적화를 위해 사용. 마지막에 System.out.println()으로 한번에 출력

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

슬라이딩 윈도우를 오른쪽으로 이동

`while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize)`

덱 앞에서 윈도우 범위에서 벗어난 인덱스 제거
예: i = 3일 때 windowSize = 3 → i - windowSize = 0 → peekFirst() <= 0이면 제거

`while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])`

덱 뒤에서 현재 높이보다 작거나 같은 인덱스 제거
이유: 더 큰 값이 오른쪽에 생기면, 그 앞의 값은 무조건 뒤짐.

`deque.offerLast(i);`

현재 인덱스를 덱에 추가

`if (i >= windowSize - 1) { sb.append(heights[deque.peekFirst()]).append(" "); }`

슬라이딩 윈도우가 완전히 구성된 순간부터 최댓값을 출력
덱의 앞에 있는 인덱스가 항상 윈도우 내에서 최댓값을 가진 인덱스

📤 실행 예시 (직접 디버깅 흐름 예)

i = 0 → 윈도우 X  
i = 1 → 윈도우 X  
i = 2 → [0,1,2] → 최대값 4  
i = 3 → [1,2,3] → 최대값 5  
i = 4 → [2,3,4] → 최대값 5  
i = 5 → [3,4,5] → 최대값 5  
i = 6 → [4,5,6] → 최대값 3  
i = 7 → [5,6,7] → 최대값 3

출력: `4 5 5 5 3 3`

좋아! 지금부터 i = 1, i = 2일 때도 너가 스스로 디버깅할 수 있도록,
deque 내부 변화, 각 조건문 통과 여부, 어떤 값이 들어가고 어떤 값이 제거되는지 전부 자세히 알려줄게.

🌟 전제 복습

N = 8, M = 2 → windowSize = 2*M - 1 = 3
heights = [2, 1, 4, 5, 1, 3, 3, 2]
현재까지 deque 상태: deque = [0]

✅ i = 1

현재 상태:

i = 1
deque = [0]
heights[1] = 1

① `while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize)`

deque.peekFirst() = 0
i - windowSize = 1 - 3 = -2

→ 0 <= -2 ? → ❌ false → 아무것도 제거 안 됨

✅ 첫 조건문: 건너뜀

② `while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])`

deque.peekLast() = 0
heights[0] = 2
heights[1] = 1

→ 2 <= 1 ? → ❌ false → 아무것도 제거 안 됨

✅ 두 번째 조건문도 건너뜀

③ `deque.offerLast(i) → deque.offerLast(1)`

→ deque = [0, 1]

✅ i = 1 요약

단계	설명
peekFirst: 0 ≤ -2 → ❌	deque 유지
heights[0] ≤ heights[1] → 2 ≤ 1 → ❌	deque 유지
i = 1 추가됨	deque = [0, 1]

✅ i = 2

현재 상태:

i = 2
deque = [0, 1]
heights[2] = 4

① `while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize)`

i - windowSize = 2 - 3 = -1
deque.peekFirst() = 0

→ 0 <= -1 ? → ❌ false → 아무것도 제거 안 됨

✅ 첫 조건문: 건너뜀

② `while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])`

여기서 아주 중요한 제거들이 일어나!

첫 반복:

deque.peekLast() = 1
heights[1] = 1
heights[2] = 4

→ 1 <= 4 → ✅ → deque.pollLast() → 제거됨 → deque = [0]

두 번째 반복:

deque.peekLast() = 0
heights[0] = 2
heights[2] = 4

→ 2 <= 4 → ✅ → deque.pollLast() → 제거됨 → deque = []

➡️ 결국 deque가 비게 됨

③ `deque.offerLast(2)` → `deque = [2]`

✅ i = 2 요약

단계	설명
peekFirst: 0 ≤ -1 → ❌	deque 유지
heights[1] ≤ 4 → ✅ 제거됨 (1 제거)
heights[0] ≤ 4 → ✅ 제거됨 (0 제거)
i = 2 추가됨	deque = [2]

✅ 시각적 흐름 정리

i	heights[i]	deque(before)	제거된 인덱스 (이유)	deque(after)
0	2	[]	없음	[0]
1	1	[0]	없음	[0, 1]
2	4	[0, 1]	1 (작음), 0 (작음)	[2]

🔍 지금까지의 흐름을 요약하면

deque는 항상 현재 윈도우 범위 내에서, 값이 큰 인덱스를 앞으로 유지하려고 함
i = 2에서는 4가 들어오면서 앞에 있는 1, 2는 더 이상 최대가 될 수 없으므로 모두 제거

✅ deque의 의미 다시 정리

deque 내부 인덱스	의미
앞쪽 인덱스	윈도우 내 최댓값을 가리킴
뒤쪽 인덱스	그보다 작은 후보들 (순서대로 정렬됨)

아주 중요한 걸 스스로 발견했어!
맞아, 이게 슬라이딩 윈도우 + 덱 알고리즘의 핵심 포인트 중 하나야:

✅ 핵심 포인트 요약

deque는 반복문 안에서 두 번의 조건문을 거쳐 필터링돼:

범위 초과된 인덱스를 제거 → 앞쪽(왼쪽) 조건

최댓값이 아닌 후보들을 제거 → 뒤쪽(오른쪽) 조건

그리고 나서 현재 인덱스를 덱에 추가

📌 왜 두 번 필터링이 필요할까?

💬 예를 들어 설명:

상황:

윈도우 크기 3
현재까지 deque = [3, 5]
다음 값 heights[6] = 3 이 들어오려고 함

① 먼저 앞쪽 인덱스 검사 (윈도우 범위에서 벗어났는지)

i - windowSize = 6 - 3 = 3
deque.peekFirst() = 3 → 범위 초과 아님 → 유지

② 다음으로 뒤쪽 인덱스들 비교 (현재 값보다 작거나 같은 애들 제거)

deque.peekLast() = 5
heights[5] = 3
heights[6] = 3

→ 같거나 작으니까 제거
→ deque.pollLast()로 5 제거됨

💡 이중 조건의 의도는 이렇게 요약돼:

조건	목적
`deque.peekFirst() <= i - windowSize`	윈도우 범위에서 벗어난 인덱스 제거 (시간 지남에 따라)
`heights[deque.peekLast()] <= heights[i]`	최댓값 후보보다 작으면 의미 없으니 제거 (덱을 "엄격한 내림차순" 유지)

🔁 이런 이중 필터 덕분에 deque는 항상 윈도우 내에서 가장 큰 값을 O(1)에 찾을 수 있어!

덕분에 전체 알고리즘이 O(N) 시간복잡도로 동작 가능해!
단순히 for + max() 쓰면 시간 초과가 나는 이유가 이거야!

✅ 예제 비유로 쉽게 요약

덱은 "현재 가장 쓸모 있는 놈들"만 남기고,
새로 들어온 강한 놈이 있으면 약한 놈들을 줄 세워서 쫓아냄.

[2, 1] ← 4가 오면: “둘 다 나가, 내가 제일 큼”
→ 남은 건 [4]

좋아! 그럼 방금까지 이어서 i = 3, i = 4일 때의 흐름을 디버깅 수준으로 이어서 완전 해부해줄게.
지금까지의 이해가 바탕이 되었으니, 더 명확하게 정리할 수 있어.

🧾 전제 상태 복습

windowSize = 3
heights = [2, 1, 4, 5, 1, 3, 3, 2]
이전 단계까지:
- i = 2까지 처리했고
- deque = [2]
- heights[2] = 4

✅ i = 3, heights[3] = 5

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

i = 3, i - windowSize = 0
deque.peekFirst() = 2
2 <= 0 → ❌ 아니므로 아무것도 제거 안 됨

while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])

heights[deque.peekLast()] = heights[2] = 4
heights[3] = 5

→ 4 <= 5 → ✅ 조건 만족 → deque.pollLast() → 2 제거

→ deque = [] 됨

deque.offerLast(3) → deque = [3]

✅ i = 3 요약 정리

단계	설명
범위 초과 확인: `2 <= 0` → ❌	제거 없음
값 비교: `4 <= 5` → ✅	인덱스 2 제거
현재 i=3 추가	deque = [3]

현재 윈도우: [4, 5, 1]
현재 윈도우 내 최댓값: heights[3] = 5

✅ i = 4, heights[4] = 1

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

i = 4, i - windowSize = 1
deque.peekFirst() = 3
3 <= 1 → ❌ → 제거 없음

while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])`

heights[deque.peekLast()] = heights[3] = 5
heights[4] = 1
5 <= 1 → ❌ → 제거 없음

deque.offerLast(4) → deque = [3, 4]

✅ i = 4 요약 정리

단계	설명
범위 초과 확인: `3 <= 1` → ❌	제거 없음
값 비교: `5 <= 1` → ❌	제거 없음
현재 i=4 추가	deque = [3, 4]

현재 윈도우: [5, 1, 3]
현재 윈도우 내 최댓값: heights[3] = 5 그대로 유지

🧠 지금까지 deque 변화 흐름

i	heights[i]	deque (after)	설명
0	2	[0]	초기값
1	1	[0, 1]	1은 2보다 작아서 추가만
2	4	[2]	2,1 제거 (4가 큼)
3	5	[3]	4 제거 (5가 더 큼)
4	1	[3, 4]	1은 작아서 뒤에 붙음

📌 시각적 정리 (deque: 인덱스를 저장하고 있음)

i = 3
deque = [2] → heights[2] = 4
→ 4 <= 5 → 제거됨
→ 추가: 3 → deque = [3]

i = 4
deque = [3]
→ 5 > 1 → 유지
→ 추가: 4 → deque = [3, 4]

🧾 이 시점에서 윈도우별 최댓값 정리

i	윈도우 (i-2 ~ i)	최대값 인덱스 (deque.peekFirst())	값
2	[2, 1, 4]	2	4
3	[1, 4, 5]	3	5
4	[4, 5, 1]	3	5

좋아! 그럼 지금까지 이어서 i = 5부터 i = 7까지 완전 디버깅해서 계산해줄게.
각 줄에서 조건문 통과 여부, deque의 변화, 왜 제거되었는지, 최종 deque 상태, 그리고 출력되는 최댓값까지 하나하나 짚어보자.

📌 전제

N = 8, M = 2 → windowSize = 3
heights = [2, 1, 4, 5, 1, 3, 3, 2]
deque = [3, 4] (i = 4까지 처리됨)
우리는 i = 5 ~ 7을 처리할 것

✅ i = 5, heights[5] = 3

① 범위 벗어난 인덱스 제거

i - windowSize = 5 - 3 = 2
deque.peekFirst() = 3 → 3 > 2 → 제거 없음

② 현재 값보다 작거나 같은 값 제거

heights[deque.peekLast()] = heights[4] = 1  
heights[5] = 3

→ 1 <= 3 → ✅ → deque.pollLast() → 4 제거됨
→ deque = [3]

heights[deque.peekLast()] = heights[3] = 5  
5 <= 3 → ❌ → 제거 안 됨

③ 현재 인덱스 추가

deque.offerLast(5) → deque = [3, 5]

✅ 윈도우 [5, 1, 3] → deque.peekFirst() = 3 → heights[3] = 5
→ 출력: 5

✅ i = 6, heights[6] = 3

① 범위 벗어난 인덱스 제거

i - windowSize = 6 - 3 = 3  
deque.peekFirst() = 3 → 3 == 3 → ✅ 제거됨  
→ deque = [5]

② 현재 값보다 작거나 같은 값 제거

heights[deque.peekLast()] = heights[5] = 3  
3 <= 3 → ✅ → 제거됨  
→ deque = []

③ 현재 인덱스 추가

deque.offerLast(6) → deque = [6]

✅ 윈도우 [1, 3, 3] → peekFirst = 6 → heights[6] = 3
→ 출력: 3

✅ i = 7, heights[7] = 2

① 범위 벗어난 인덱스 제거

i - windowSize = 7 - 3 = 4  
deque.peekFirst() = 6 → 6 > 4 → 제거 없음

② 현재 값보다 작거나 같은 값 제거

heights[deque.peekLast()] = heights[6] = 3  
3 <= 2 → ❌ → 제거 없음

③ 현재 인덱스 추가

deque.offerLast(7) → deque = [6, 7]

✅ 윈도우 [3, 3, 2] → peekFirst = 6 → heights[6] = 3
→ 출력: 3

🎯 최종 결과

i	윈도우	deque 상태	출력값
2	[2, 1, 4]	[2]	4
3	[1, 4, 5]	[3]	5
4	[4, 5, 1]	[3, 4]	5
5	[5, 1, 3]	[3, 5]	5
6	[1, 3, 3]	[6]	3
7	[3, 3, 2]	[6, 7]	3

✅ 최종 출력

4 5 5 5 3 3

🔍 deque 변화 요약

i	설명
2	1, 0 제거 → 2만 남음
3	2 제거 → 3만 남음
4	값 작으므로 유지 → 4 추가
5	1(4) 제거 → 5 추가
6	3(3) 제거 → 6 추가
7	2는 작으므로 그냥 추가

좋아! 그럼 최종 출력값인 4 5 5 5 3 3 이 도대체 어떻게 나왔는지를
각 i에서 슬라이딩 윈도우의 범위, deque 내부 인덱스, 그 인덱스에 해당하는 heights 값, 그리고 출력되는 최대값이 왜 그것인지까지 디버깅 방식으로 완전하게 설명해줄게.

📌 전제 복습

N = 8, M = 2 → windowSize = 2 * M - 1 = 3
heights = [2, 1, 4, 5, 1, 3, 3, 2]

출력은 언제 시작되냐면?

if (i >= windowSize - 1) {
    sb.append(heights[deque.peekFirst()]).append(" ");
}

→ 즉, i = 2부터 시작해서 i = 7까지 출력됨
→ 총 출력값 6개

🧾 deque에는 "인덱스"가 들어 있고,

출력은 heights[deque.peekFirst()]로 "최댓값을 가진 인덱스"를 꺼내서 그 값을 출력해.

✅ i = 2 → 윈도우 [0,1,2]

heights = [2, 1, 4]
이 시점 deque = [2]
deque.peekFirst() = 2 → heights[2] = 4

→ ✅ 출력: 4

✅ i = 3 → 윈도우 [1,2,3]

heights = [1, 4, 5]
이 시점 deque = [3]
peekFirst = 3 → heights[3] = 5

→ ✅ 출력: 5

✅ i = 4 → 윈도우 [2,3,4]

heights = [4, 5, 1]
deque = [3, 4] (3은 5, 4는 1)
peekFirst = 3 → heights[3] = 5

→ ✅ 출력: 5

✅ i = 5 → 윈도우 [3,4,5]

heights = [5, 1, 3]
deque = [3, 5] (3은 5, 5는 3)
peekFirst = 3 → heights[3] = 5

→ ✅ 출력: 5

✅ i = 6 → 윈도우 [4,5,6]

heights = [1, 3, 3]
deque = [6]
peekFirst = 6 → heights[6] = 3

→ ✅ 출력: 3

✅ i = 7 → 윈도우 [5,6,7]

heights = [3, 3, 2]
deque = [6, 7]
peekFirst = 6 → heights[6] = 3

→ ✅ 출력: 3

✅ 최종 요약표

i	윈도우 구간	heights[구간]	deque	최대 인덱스	출력값
2	[0,1,2]	[2,1,4]	[2]	2	4
3	[1,2,3]	[1,4,5]	[3]	3	5
4	[2,3,4]	[4,5,1]	[3,4]	3	5
5	[3,4,5]	[5,1,3]	[3,5]	3	5
6	[4,5,6]	[1,3,3]	[6]	6	3
7	[5,6,7]	[3,3,2]	[6,7]	6	3

🔍 왜 peekFirst()만 보면 되냐?

deque는 항상 내림차순(값 기준) 으로 유지되기 때문에
→ 가장 앞에 있는 인덱스가 항상 "현재 윈도우 내 최댓값의 인덱스"다!
따라서 출력은 항상 heights[deque.peekFirst()]

✅ 최종 출력

4 5 5 5 3 3

류한선

good

이전 포스트

스코프 연습(람다 대부분,지역 클래스 변수 변경),int =가 불변인건 다른 메서드에서 사용할시 불변이고 같은 클래스의 메서드내는 수정 ok

다음 포스트

달려라 홍준

실기연습-2

🔍 문제 핵심 요약

📥 입력 예제 (내가 정함)

✅ Java 전체 코드 (Deque 이용 슬라이딩 윈도우 최댓값)

🔬 코드 라인별 상세 해설 + 예제 흐름 분석

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

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

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

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

int[] heights = new int[N];

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

for (int i = 0; i < N; i++) { heights[i] = Integer.parseInt(st.nextToken()); }

int windowSize = 2 * M - 1;

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

StringBuilder sb = new StringBuilder();

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

슬라이딩 윈도우를 오른쪽으로 이동

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

while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])

deque.offerLast(i);

if (i >= windowSize - 1) { sb.append(heights[deque.peekFirst()]).append(" "); }

📤 실행 예시 (직접 디버깅 흐름 예)

🌟 전제 복습

✅ i = 1

현재 상태:

① while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize)

② while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])

③ deque.offerLast(i) → deque.offerLast(1)

✅ i = 1 요약

✅ i = 2

현재 상태:

① while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize)

② while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])

③ deque.offerLast(2) → deque = [2]

✅ i = 2 요약

✅ 시각적 흐름 정리

🔍 지금까지의 흐름을 요약하면

✅ deque의 의미 다시 정리

✅ 핵심 포인트 요약

📌 왜 두 번 필터링이 필요할까?

💬 예를 들어 설명:

상황:

① 먼저 앞쪽 인덱스 검사 (윈도우 범위에서 벗어났는지)

② 다음으로 뒤쪽 인덱스들 비교 (현재 값보다 작거나 같은 애들 제거)

💡 이중 조건의 의도는 이렇게 요약돼:

🔁 이런 이중 필터 덕분에 deque는 항상 윈도우 내에서 가장 큰 값을 O(1)에 찾을 수 있어!

✅ 예제 비유로 쉽게 요약

🧾 전제 상태 복습

✅ i = 3, heights[3] = 5

✅ i = 3 요약 정리

✅ i = 4, heights[4] = 1

✅ i = 4 요약 정리

🧠 지금까지 deque 변화 흐름

📌 시각적 정리 (deque: 인덱스를 저장하고 있음)

🧾 이 시점에서 윈도우별 최댓값 정리

📌 전제

✅ i = 5, heights[5] = 3

① 범위 벗어난 인덱스 제거

② 현재 값보다 작거나 같은 값 제거

③ 현재 인덱스 추가

✅ i = 6, heights[6] = 3

① 범위 벗어난 인덱스 제거

② 현재 값보다 작거나 같은 값 제거

③ 현재 인덱스 추가

✅ i = 7, heights[7] = 2

① 범위 벗어난 인덱스 제거

② 현재 값보다 작거나 같은 값 제거

③ 현재 인덱스 추가

🎯 최종 결과

✅ 최종 출력

🔍 deque 변화 요약

📌 전제 복습

🧾 deque에는 "인덱스"가 들어 있고,

✅ i = 2 → 윈도우 [0,1,2]

✅ i = 3 → 윈도우 [1,2,3]

✅ i = 4 → 윈도우 [2,3,4]

✅ i = 5 → 윈도우 [3,4,5]

✅ i = 6 → 윈도우 [4,5,6]

✅ i = 7 → 윈도우 [5,6,7]

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

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

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

`int M = Integer.parseInt(st.nextToken());`

`int[] heights = new int[N];`

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

`for (int i = 0; i < N; i++) { heights[i] = Integer.parseInt(st.nextToken()); }`

`int windowSize = 2 * M - 1;`

`Deque<Integer> deque = new LinkedList<>();`

`StringBuilder sb = new StringBuilder();`

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

`while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize)`

`while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])`

`deque.offerLast(i);`

`if (i >= windowSize - 1) { sb.append(heights[deque.peekFirst()]).append(" "); }`

① `while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize)`

② `while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])`

③ `deque.offerLast(i) → deque.offerLast(1)`

① `while (!deque.isEmpty() && deque.peekFirst() <= i - windowSize)`

② `while (!deque.isEmpty() && heights[deque.peekLast()] <= heights[i])`

③ `deque.offerLast(2)` → `deque = [2]`