첫 번째 풀이 - 우선순위큐 + 슬라이딩 윈도우 + 해시테이블(카운팅 용도)

우선, 아래 코드는 정확성테스트는 모두 통과했지만, 효율성이 모두 틀렸다.
다만, 시간복잡도가 얼추(여기서 얼추인 이유는 해시테이블을 사용해서임) 계산했을때 N=최대20만인 상황에서, O(NlogN)이므로 실패할 이유가 없어보였다.
이 문제의 시간 복잡도가 타이트한 것으로 예상이된다. 또한 '질문하기'탭을 들어가보니, 나와 비슷하게 풀어서 고민을 하는 사람들이 많았다.

해시테이블을 사용해서 발생하는 (비교적 복잡한)해싱함수 연산 과정과 해시충돌 해결 과정 등에서 시간이 많이 소모됐을 가능성도 있으나, 근본적으로 이 문제에서 원하는 풀이는 이분탐색인 것으로 예상된다.
추가) 그래서, 맨 아래에 해시테이블을 사용하지 않도록 개선한 코드를 실행했더니 통과했다.

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        // 최대힙 필요함.
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a1,a2) -> {
            return a2-a1;
        });
        HashMap<Integer, Integer> count = new HashMap();
        for (int i=0; i<k; i++) {
            count.put(stones[i], count.getOrDefault(stones[i], 0)+1);
            pq.add(stones[i]);
        }
        int init = pq.poll();
        answer = init;
        pq.add(init);
        
        for (int i=1; i<=stones.length-k; i++) {
            int rangeMin = 10_0000_0000;
            pq.add(stones[i-1+k]);
            count.put(stones[i-1+k], count.getOrDefault(stones[i-1+k], 0)+1);
            count.put(stones[i-1], count.get(stones[i-1])-1);
            
            while(!pq.isEmpty()) {
                int tmp = pq.poll();
                if(count.getOrDefault(tmp, 0) == 0) continue;
                rangeMin = tmp;
                pq.add(tmp);
                break;
            }
            
            answer = Math.min(answer, rangeMin);
        }
        return answer;
    }
}

두 번째 풀이 - 이분탐색

우선, 위 첫 풀이에서 실패하고 '질문하기'탭에서 이분탐색이라는 아이디어를 얻었다.
건널 수 있는 사람의 수를 mid로 잡고, 건널 수 있는지 검사를 logN 번 하면 된다.
위의 첫 풀이에서 슬라이딩 윈도우의 크기를 k로 잡고 해당 구간의 최댓값을 탐색했음.
즉, 연속된 k길이 구간 내에서 mid명 이상의 사람이 건널 수 있는 돌이 하나는 있어야 한다. 만약 이걸 만족하지 않는 구간이 있다는 것은 mid명이 건너지 못한다는 것을 의미한다.

import java.util.*;

class Solution {
    int[] stones;
    int k;
    public int solution(int[] stones, int k) {
        this.stones = stones;
        this.k = k;
        
        int answer = 0;
        int l = 0;
        int r = 2_0000_0000;
        while(l<=r){
            int mid = (l+r)/2;
            if (isPromise(mid)) {
                l = mid+1;
                answer = Math.max(answer, mid);
            } else {
                r = mid-1;
            }
        }
        return answer;
    }
    
    boolean isPromise(int n) {
        int continuousFailed = 0;
        for(int i=0; i<stones.length; i++){
            if(stones[i] < n) {
                continuousFailed++;
            } else {
                continuousFailed = 0;
            }
            
            if (continuousFailed >= k) return false;
        }
        return true;
    }
}

첫 번째 풀이 개선 - 해시테이블 제거

기존에 갯수를 세는 것 대신, 인덱스 기반으로 이 PQ에서 뽑은 값이 유효한 값인지 구분하도록 수정했다.

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        int answer = 0;
        // 최대힙 필요함.
        PriorityQueue<Stone> pq = new PriorityQueue<Stone>((s1,s2) -> {
            if (s1.value != s2.value){
                return s2.value - s1.value;
            } else {
                return s1.index - s2.index; // 인덱스 작은게 먼저 나오도록 
            }
        });
        
        for (int i=0; i<k; i++) {
            pq.add(new Stone(i, stones[i]));
        }
        Stone s = pq.poll();
        answer = s.value;
        int maxValue = s.value;
        int maxIndex = s.index;
        pq.add(s);
        
        for (int i=1; i<=stones.length-k; i++) {
            pq.add(new Stone(i-1+k, stones[i-1+k]));
            if(maxIndex < i) {
                while(!pq.isEmpty()) {
                    Stone tmp = pq.poll();
                    if(tmp.index < i) continue;
                    maxValue = tmp.value;
                    maxIndex = tmp.index;
                    pq.add(tmp);
                    break;
                }
                answer = Math.min(answer, maxValue);
            } else {
                if(maxValue < stones[i-1+k]) {
                    maxValue = stones[i-1+k];
                    maxIndex = i-1+k;
                }
            }
        }
        return answer;
    }
}

class Stone {
    final int index;
    final int value;
    Stone(int index,int value) {
        this.index = index;
        this.value = value;        
    }
}

다만, 시간자체는 이분탐색이 더 빠르다.
그래도 이번 기회로 해시테이블의 잠재적 위험성?을 접했기에 재밌었다.