더맵게(Priority Queue, Min Heap)

 

최근에 풀던 문제보다 정답률이 더 낮은문젠데, 왜 이렇게 쉽지? 싶었다. 항상 처음에는 오 쉽네ㅋㅋ했긴했는데 막상 풀다보면 어려운 그런 문제들이 많았어서 이것도 그런가보다 했는데 풀다보니 진짜 쉬워서 왜쉽지?? 하고 테스트를 돌려보니.. 효율성테스트가 있는 문제였다.

그럼 그렇지

 

내가 처음 푼 코드를 보자.

public static int solution(int[] scoville, int K) {
        //몇번 믹스할지
        int cnt = 0;
		//moreThanK가 true를 반환할때까지 mix해주고 카운트 갯수세줌.
        while (!moreThanK(scoville, K)) {
            scoville = mix(scoville);
            cnt++;
			//만약 스코빌이 하나남았는데도 K보다 작다면 -1 반환해줌.
            if (scoville.length == 1 && scoville[0] < K) {
                return -1;
            }
        }

        return cnt;
    }
    //scoville 순회하면서 하나라도 K보다 작으면 false, 모두다 K이상이면 true
    public static boolean moreThanK(int[] scoville, int K) {
        for (int scov : scoville) {
            if (scov < K) {
                return false;
            }
        }
        return true;
    }
    //문제설명대로 섞어주는 메서드.
    //한번섞으면 길이가 하나 줄어드므로 sco2를 만들어서 섞고 넣어줬다.
    public static int[] mix(int[] sco){
        if(sco.length == 1){
            return sco;
        }
        int[] sco2 = new int[sco.length-1];
        Arrays.sort(sco);
        sco2[0] = sco[0] + sco[1] * 2;
        for (int i = 2, j = 1; i < sco.length; i++) {

                sco2[j] = sco[i];
                j++;

        }
        return sco2;
    }

 

꽤나 쉽게 풀었다. 하지만, 효율성테스트를 하나도 통과하지 못했다.

그래서 알아보니, Min Heap을 이용해 풀어야만 효율성 테스트를 통과한다고 한다.

일단 정답 코드 부터 보자.

public static int solution(int[] scoville, int K) {
    int cnt = 0;
    PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
	//scoville의 모든 요소를 priorityQue 에 집어넣는다.
    for (int scov : scoville) {
        priorityQueue.offer(scov);
    }
	//priorityQueue 에서 가장작은 요소가 K이상이될때까지 반복
    while (priorityQueue.peek() < K) {
        if (priorityQueue.size() < 2) {
            return -1; // 섞을 수 없는 상황
        }
		//가장작은 두요소 추출해서 섞고 mixedScoville에 저장함.
        int min1 = priorityQueue.poll();
        int min2 = priorityQueue.poll();
        int mixedScoville = min1 + (min2 * 2);
        priorityQueue.offer(mixedScoville);
        cnt++;
    }

    return cnt;
}

여기서 드는 의문은

while (priorityQueue.peek() < K) { 
	if (priorityQueue.size() < 2) { 
    	return -1; // 섞을 수 없는 상황 
    } 
    int min1 = priorityQueue.poll();
    int min2 = priorityQueue.poll(); 
    int mixedScoville = min1 + (min2 * 2); 
    priorityQueue.offer(mixedScoville); cnt++; 
    }

이부분에서 가장 작은 두 요소를 추출해서 섞고 다시 offer(mixesScoville) 하면 보통 힙과 다르게 Min Heap의 속성에 따라 새로운 요소가 우선순위에 따라 정렬된다고 한다.

예를 들어, 1,2,12,14,15,16 이 처음 priorityQueue 인 경우에, 첫반복에서 min1 = 1, min2 = 2; mixedScoville은 5가 되고, priorityQueue.offer(5) 하면 priorityQueue는 내부적으로 정렬을해서 5,12,14,15,16이 남게된다.

Priority Queue는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는것을 말한다고 한다.

 

큐지만 내부정렬이 되는 큐라... 신기했다.

 

힙(Heap)과 우선순위 큐에대해 잘 정리한 블로그다.

https://chanhuiseok.github.io/posts/ds-4/

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

https://velog.io/@chosj1526/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-Priority-Queue-%EC%A0%95%EB%A0%AC-%EC%A0%84%EB%9E%B5-%EC%84%A4%EC%A0%95%EB%B2%95

[자료구조] 우선순위 큐 (Priority Queue) + 정렬 전략 설정법