[프로그래머스/Java] 징검다리 건너기

 

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

프로그래머스

 

for문(시간 초과), 슬라이딩 윈도우(시간 초과)

카카오 공식 해설은 이분 탐색을 이용하라고 적혀 있었지만, 하기 싫었다. (..)

질문 게시판을 보니, leetcode의 Sliding Window Maximum 문제와 유사하게 풀면 된다고 한다.

 

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        Deque<int[]> deque = new ArrayDeque<>();
        int size = stones.length;
        int answer = Integer.MAX_VALUE;
        
        for (int i=0; i<k; i++) {
            while (!deque.isEmpty() && deque.getLast()[1] < stones[i]) {
                deque.removeLast();
            }
            
            deque.add(new int[]{i, stones[i]});
        }
        
        answer = Math.min(answer, deque.getFirst()[1]);
        
        for (int i=k; i<size; i++) {
            if (!deque.isEmpty() && deque.getFirst()[0] == i-k) {
                deque.removeFirst();
            }
            
            while (!deque.isEmpty() && deque.getLast()[1] < stones[i]) {
                deque.removeLast();
            }
            
            deque.add(new int[]{i, stones[i]});
            
            answer = Integer.min(answer, deque.getFirst()[1]);
        }
        
        return answer;
    }
}

 

Deque를 이용했다. (원소를 앞뒤로 넣고 뺄 수 있다.)

 

앞에서부터 k개는

1. 새로 들어오는 원소보다 작은 것들을 뒤에서부터 빼준다.

(새로 들어오는 값보다 작은 값들은 최댓값이 될 수 없기 때문이다.)

2. 새로 들어오는 원소를 넣어준다.

3. 1-2를 k번 반복 후, Deque의 가장 첫 번째 원소와 정답 비교.

(가장 첫 번째 원소가 최댓값이 된다.)

 

이후 나머지 원소들에 대해

1. Deque의 맨 앞 원소의 인덱스가 현재 범위를 벗어나면 지운다.

2. 새로 들어오는 원소보다 작은 것들을 뒤에서부터 빼준다.

3. 새로 들어오는 원소를 넣어준다.

4. Deque의 가장 첫 번째 원소와 정답 비교.

5. 1-4를 원소의 수만큼 반복.