[프로그래머스, 64062] 징검다리 건너기 (java)

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

프로그래머스

728x90

---

메모리: 67.1 MB, 시간: 92.76 ms

사용 알고리즘: 우선순위 큐, 그리디 알고리즘

 

건널 수 있는 친구들은 모두 건너고, 마지막 친구가 건너는 상황이라고 가정

현재 위치 point에서 k칸 내에 있는 디딤돌 중, 가장 숫자가 큰 디딤돌로 이동

징검다리를 건널 때까지 항상 범위 내 가장 숫자가 큰 디딤돌로 이동한다.

밟은 디딤돌 중 숫자가 가장 작은 디딤돌이 사라지면, 더 이상 다른 친구가 건널 수 없다.

따라서 밟은 디딤돌 중 숫자가 가장 작은 디딤돌의 숫자가 징검다리를 마지막으로 건넌 친구의 순번이다.

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        
        // 점프할 수 있는 거리의 디딤돌의 숫자 순으로 내림차순 정렬할 큐
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[0] - o1[0]);
        
        // 현재 위치
        int point = -1;
        
        // 마지막으로 큐에 넣은 디딤돌 위치
        int visited = -1;
        
        // 항상 최선의 위치로 이동했을 때의 최솟값
        int answer = Integer.MAX_VALUE;
        
        int[] next;
        while(point + k < stones.length) {
            
            // 현재 위치에서 점프할 수 있는 디딤돌들 큐에 넣어줌
            for(int i = visited + 1; i <= point + k; i++) {
                pq.add(new int[] {stones[i], i});
            }
            visited = point + k;
            
            // 다음에 이동할 디딤돌 고르기
            next = new int[] {0, -2};
            while(next[1] < point) next = pq.poll(); // 이미 뛰어넘은 곳은 넘어감
            
            // 다음으로 이동할 디딤돌 위치
            point = next[1];
            
            // 건넌 디딤돌 중 최솟값 저장
            answer = Math.min(answer, next[0]);
        }
        
        
        return answer;
    }
}