문제

https://school.programmers.co.kr/learn/courses/30/lessons/64062

---

입력

디딤돌에 적힌 숫자가 순서대로 담긴 배열 stones와 한 번에 건너뛸 수 있는 디딤돌의 최대 칸수 k

---

출력

최대 몇 명까지 징검다리를 건널 수 있는지

---

풀이

제한조건

• 징검다리를 건너야 하는 니니즈 친구들의 수는 무제한 이라고 간주합니다.
• stones 배열의 크기는 1 이상 200,000 이하입니다.
• stones 배열 각 원소들의 값은 1 이상 200,000,000 이하인 자연수입니다.
• k는 1 이상 stones의 길이 이하인 자연수입니다.

접근방법

stones의 크기가 200,000 이하로 주어져있고, 문제 상단에 효율성 테스트가 있다고 나와있다.
즉 N^2 알고리즘을 사용하면 효율성에서 실패한다.

슬라이딩 윈도우
슬라이딩 윈도우를 통해 k개 만큼씩 윈도우를 확인하며 검사를 해본다.

1. k개를 보는 윈도우를 만든다.
2. 각 윈도우에서 최대값을 구한다.
3. 윈도우를 이동한다.
4. 현재 윈도우의 최대값과 이전 윈도우의 최대값 중 작은 값을 선택한다.
5. 2~4과정을 반복한다.

각 윈도우의 최대값(x라고 하자)을 구하는 이유는 x명이 지나갈 경우 해당 윈도우에 모든 돌이 0이 되므로 k칸을 건너 뛰는게 불가능해지기 때문이다.

따라서 모든 윈도우의 최대값중 최소값이 정답이 된다.

코드로 구현시 Deque에 들어갈 데이터는 인덱스 정보이다.
보통 자료구조에 값을 넣어서 처리하는 경우가 많지만, 값을 넣어서 처리하게 된다면 값을 비교하는 과정과 윈도우에서 추가 및 제거되어야 할 부분을 관리하는게 까다롭다.

인덱스 정보를 알고 있다면, 값을 바로 찾을 수 있기때문에 인덱스 정보를 관리하고 항상 최대값을 가진것이 deque의 가장 앞으로 올 수 있게 구현하자.

---

코드

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        int len = stones.length;
        // 인덱스 정보만 담는다.
        Deque<Integer> dq = new ArrayDeque<>();
        int max = Integer.MAX_VALUE;
        
        for(int i = 0; i < len; ++i){
            // 윈도우에서 벗어난 원소 제거
            while(!dq.isEmpty() && dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            // 새로운 원소가 기존의 원소들보다 크면, 작은 원소들 제거
            while(!dq.isEmpty() && stones[dq.peekLast()] < stones[i]) {
                dq.pollLast();
            }
            dq.addLast(i);
            // 각 윈도우에서 최대값 중 최소가 마지막으로 건너뛰어 갈 수 있는 사람 수이다.
            if(i >= k - 1) {
                max = Math.min(max, stones[dq.peekFirst()]);
            }
        }
        
        return max;
    }
}