[Programmers] 징검다리 건너기

문제

 

2019 카카오 개발자 겨울 인턴십 > 징검다리 건너기

코딩테스트 연습 - 징검다리 건너기

 

 

아이디어

 

이번 문제는 우선순위 큐와 일반 큐의 조합으로 풀어봤습니다.

 

제가 문제를 읽고 생각한 풀이 방법은 "디딤돌을 k개만큼 순서대로 묶었을 때 묶어진 디딤돌들에서 나오는 최댓값들 중 최솟값을 구하기"였습니다.

 

왜냐하면 k개 만큼 인접한 디딤돌들은 서로 커버가 가능하기 때문입니다.

 

그렇기 때문에 인접한 디딤돌들을 k개만큼 묶으면 묶인 디딤돌들은 내부에 존재하는 디딤돌의 최댓값만큼 버틸 수 있고 결국에는 묶인 디딤돌들의 최댓값 중 최솟값을 구하면 최대 건널 수 있는 카카오 친구들의 숫자를 구할 수 있게 됩니다.

 

1번 테스트 케이스로 예시를 들면 다음과 같이 구해지게 됩니다.

 

1번째 묶여지는 디딤돌과 최댓값: [2, 4, 5], 5

2번째 묶여지는 디딤돌과 최댓값: [4, 5, 3], 5

 

.

.

.

 

4번째 묶여지는 디딤돌과 최댓값: [3, 2, 1], 3

 

.

.

.

 

그리고 이렇게 구해진 최댓값들 중 최솟값은 3이기 때문에 정답은 3이 되는 것입니다.

 

코드로 구현해보면 다음과 같습니다.

 

 

구현 코드 (Java)

 

import java.util.*;

class Solution {
    public int solution(int[] stones, int k) {
        PriorityQueue<Node> pqueue = new PriorityQueue<>(new Comparator<Node>() { // 디딤돌 숫자로 내림차순
        	@Override
        	public int compare(Node o1, Node o2) {
        		return o2.val - o1.val;
        	}
		});
        
        Queue<Node> queue = new LinkedList<Node>(); // 디딤돌 방문 순서대로 담는 queue
        
        for(int i=0; i<k; i++) { // 초기화, k개만큼 디딤돌 pqueue, queue에 담기
        	Node node = new Node(i, stones[i]);
        	pqueue.add(node);
        	queue.add(node);
        }
        
        int res = pqueue.peek().val; // 결과값 초기화
        
        for(int i=k; i<stones.length; i++) {
        	pqueue.remove(queue.poll()); // 가장 좌측에 있는 디딤돌 queue와 pqueue에서 제거
            // 새로운 디딤돌 추가
        	Node node = new Node(i, stones[i]);
        	pqueue.add(node);
        	queue.add(node);
        	
        	res = Math.min(res, pqueue.peek().val); // pqueue에 담긴 디딤돌 중 숫자가 가장 큰 값을 이용하여 최솟값 구하기
        }
        
        return res;
    }
    
    private static class Node {
    	int index, val;

		public Node(int index, int val) {
			this.index = index;
			this.val = val;
		}
    }
}

 

 

 

읽어주셔서 감사합니다.