[프로그래머스] 라면공장 (java) Heap

2020-01-08

라면공장 (programers > lev2 > Stack_Queue)

라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다.

해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다.

현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 return 하도록 solution 함수를 완성하세요.

dates[i]에는 i번째 공급 가능일이 들어있으며, supplies[i]에는 dates[i] 날짜에 공급 가능한 밀가루 수량이 들어 있습니다.

제한사항

stock에 있는 밀가루는 오늘(0일 이후)부터 사용됩니다.
stock과 k는 2 이상 100,000 이하입니다.
dates의 각 원소는 1 이상 k 이하입니다.
supplies의 각 원소는 1 이상 1,000 이하입니다.
dates와 supplies의 길이는 1 이상 20,000 이하입니다.
k일 째에는 밀가루가 충분히 공급되기 때문에 k-1일에 사용할 수량까지만 확보하면 됩니다.
dates에 들어있는 날짜는 오름차순 정렬되어 있습니다.
dates에 들어있는 날짜에 공급되는 밀가루는 작업 시작 전 새벽에 공급되는 것을 기준으로 합니다. 예를 들어 9일째에 밀가루가 바닥나더라도, 10일째에 공급받으면 10일째에는 공장을 운영할 수 있습니다.
밀가루가 바닥나는 경우는 주어지지 않습니다.

입출력 예

stock	dates	supplies	k	result
4	[4,10,15]	[20,5,10]	30	2

입출력 예 설명

현재 밀가루가 4톤 남아 있기 때문에 오늘과 1일 후~3일 후까지 사용하고 나면 모든 밀가루를 다 사용합니다. 따라서 4일 후에는 반드시 밀가루를 공급받아야 합니다.
4일째 공급받고 나면 15일 이후 아침에는 9톤의 밀가루가 남아있게 되고, 이때 10톤을 더 공급받으면 19톤이 남아있게 됩니다. 15일 이후부터 29일 이후까지 필요한 밀가루는 15톤이므로 더 이상의 공급은 필요 없습니다.
따라서 총 2회의 밀가루를 공급받으면 됩니다.

풀이

    public static int solution(int stock, int[] dates, int[] supplies, int k) {
        int answer = 0;
        
        //원래는 오름차순인 pq를 내림차순으로 바꿔준다.
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.reverseOrder());
        
        int idx = 0; //dates의 개수만큼만 작동하게 한다. i를 활용하면 k-1까지 가니까 다른 변수 사용해야함
        
        for(int i=0;i<k;i++) {//i는 하루하루 지나는 날짜, k-1만큼만 돈다.
        	//아 들어가지않아도 dates[3]을 검사하면서 이미 error!!!!
        	if(idx < dates.length &&i == dates[idx]){//dates는 정렬되어있으므로 dates[0], dates[1], dates[2]..
        		pq.offer(supplies[idx]); // 같은 위치에 있는 supplies[0], supplies[1],,,을 pq에 넣고
        		idx++;//다음 data를 위해 idx는 증가시킨다.
        	}
        	
        	if(stock == 0) {//0이 되면 새로운 pq의 새로운 supplies를 충전해야하고 이때 맨앞에있는 값이 제일 크므로 stock에 더해줌
        		stock = stock+ pq.poll();
        		answer++; //pq에서 빠질 때마다 해외에서 공급해오는 것이기때문에 answer+1
        	}
        	
        	//for문 한번 돌때마다 무조건 stock은 -1
        	stock = stock-1;
        }
        
        
        return answer;
    }
    
	public static void main(String[] args) {
		int dates[] = {4,10,15};
		int supplies[] = {20,5,10};
		
		System.out.println(solution(4,dates,supplies,30));
	}

후기

Heap은 우선순위 큐에 사용되는 자료구조이고 java에서는 PriorityQueue로 구현할 수 있다. 루트에 제일 작은 원소가 들어가는 min heap과 루트에 제일 큰 값이 들어가는 max heap으로 되어있고, 구현되어있는 PQ는 오름차순인 min heap으로 되어있다.

처음엔 supplies와 dates가 함께 움직여야한다고 생각했다. supplies의 값들이 내림차순으로 정렬되고 dates도 함께 움직여야 한다고 생각했지만 dates가 순서대로 정렬되어있기 때문에 dates에 따른 supplies값을 PQ에 넣고 그중 제일 큰 값만 Stock==0 일 때 꺼내주면 문제는 쉽게 해결 되었다.

문제를 이해하는데 생각보다 오래 걸렸지만 한 번 이해하고 나면 쉽게 풀 수 있었고 문제 속에 힌트가 있었다.

tip

pq에 supplies에 넣어준다.
Java에서 Heap(PriorityQueue)는 오름차순으로 되어있고 내림차순으로 사용하기 위해서는 Comparator를 사용해야한다.
idx < dates.length 필수! if문에 걸리고 dates[idx++] IndexBoundError가 생긴다! 조심!
i는 날짜로 사용한다! (for문 한 번이면 해결된다)

 [프로그래머스] 프린터 (java) Queue [프로그래머스] 최솟값 만들기 (java) Max_Min 