[알고리즘] 징검다리 건너기 (프로그래머스 Level3)

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

 우선 stones 배열의 최대 크기가 20만이기 때문에 O(N) 시간 만에 처리를 해야 한다.

 

Solution

 친구들이 뛰어넘을 수 있는 길이는 K만큼이라고 했으니 어느 구간이라도 연속 K개의 돌이 0이 되는 순간 친구들은 더 이상 다리를 건널 수 없다.

 즉 배열에 존재하는 K 길이만큼의 구간들 중, 각 구간마다 포함하고 있는 돌의 최댓값이 모든 구간들 중 최솟값이 되는 경우를 찾아야 한다. 이게 무슨 말이냐면

 

 위의 예시 문에서의 K는 3이다. 해당 배열에서 길이가 3인 구간은 총 8개가 나온다.

 

Start Index	Finish Index	Max Value
0	2	5
1	3	5
2	4	5
3	5	3
4	6	4
5	7	4
6	8	5
7	9	5

 이 중 최댓값이 모든 구간 중 최소가 되는 구간은 [3, 5]이고 그 값은 3이다. 즉 제일 빨리 3개의 스톤이 0이 되는 구간이라는 뜻이다. 해당 구간에서 모든 스톤이 0이 될 때까지는 3명이 지나가야 하고 그렇기에 정답은 최대 3명이 되는 것이다.

 

import java.util.*;


class Solution {

	HashMap<Integer, Integer> count = new HashMap<>();

	public int solution(int[] stones, int k) {

		int front = 0;
		int end = front + k;

		PriorityQueue<Integer> max_heap = new PriorityQueue<>((o1, o2) -> o2 - o1);
		PriorityQueue<Integer> min_heap = new PriorityQueue<>();

		for(int i = 0;i < k;i++)
		{
			max_heap.offer(stones[i]);
			count.putIfAbsent(stones[i], 0);
			count.computeIfPresent(stones[i], (key, value) -> ++value);
		}

		//돌 연속 k개가 0이 되는 시간이 젤 빠른 구간
		min_heap.offer(max_heap.peek());
		
		//System.out.println(front +" "+ end+ " : "+max_heap.peek());
		front++;
		end++;
		while(end <= stones.length)
		{
			//빠진 돌 개수 낮춤
			count.computeIfPresent(stones[front-1], (key, value) -> --value);
			if(stones[front - 1] == max_heap.peek())
				max_heap.poll();

			//들어온 돌 개수 올림
			count.putIfAbsent(stones[end-1], 0);
			count.computeIfPresent(stones[end-1], (key, value) -> ++value);
			max_heap.offer(stones[end-1]);

			while(!max_heap.isEmpty() && count.get(max_heap.peek()) == 0)
				max_heap.poll();

			//System.out.println(front +" "+ end+ " : "+max_heap.peek());

			min_heap.offer(max_heap.peek());

			end++;
			front++;
		}


		return min_heap.poll();
	}
}