8. 더 맵게 (프로그래머스, 힙 Level 2)

* 문제 설명

 - 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.

 - 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이

   특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

- Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
- Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를

  K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항

• scoville의 길이는 2 이상 1,000,000 이하입니다.
• K는 0 이상 1,000,000,000 이하입니다.
• scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

* 입출력 예

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

 

이번 문제는 뭔지 몰라도 조건의 숫자 크기가 큰 것으로 보아 "효율성"을 얼마나 풀어낼 것인가에 대한 문제로 접근하였습니다.

힙(Heap)이라는 용어가 튀어나와 2진화 트리(이진트리, 바이너리트리) 형태로 데이터를 정렬하면 될 것 같아서 무작정 접근 했습니다.

먼저 개념을 정리 했습니다.

 1) 데이터를 정렬 한다.

 2) 맨 처음 데이터[0]를 가져와서 다음 데이터[1]와 "섞는 방법" 에 따라 데이터를 변경 한다.

 3) 만약 해당 값이 찾는 값과 일치하면 종료한다.

 4) 일치하지 않으면 처음 값은 음수처리하고, "섞는 방법"에 따라 변경한 데이터를 다음 데이터[1]에 넣어준다.

 5) 데이터를 정렬한다.

 6) 답을 찾을 때 까지 위 5단계를 반복한다.

 

위 내용을 코드로 작성하여 보았습니다.

    //섞는 메소드 입니다.
    public static int sum(int[] scoville, int index){
        int sum = scoville[index] + scoville[index + 1] * 2;
        return sum;
    }
    
    //찾는 메소드 입니다.
    public static int solution(int[] scoville, int K) {
        int answer = 0;

        int i = 0;
        int minus = -1;
		
        Arrays.sort(scoville);  //1) 정렬합니다.
        
        while (true) {
            if (scoville.length == i + 1) { //2) 데이터의 끝까지 동작하게 합니다.
                int lastSum = scoville[i];
                if (lastSum < K) {
                    answer = -1;
                }
                break;
            }

            if (scoville[i] >= K) {  //3) 더하기 전 값이 스코빌보다 높으면 종료 합니다.
                break;
            }
			
            int sum = sum(scoville, i);  //4) 스코빌 지수를 위해 앞, 뒤를 공식에 의해 합칩니다.
            scoville[i + 1] = sum;  //5) 합친 값을 넣어주고
            scoville[i] = minus;  //6) 앞에 값은 합쳐졌으므로 음수처리 합니다.
			
            Arrays.sort(scoville);  //7) 재정렬 합니다.
            answer++;
            i++;
            minus--;
        }
        return answer;
    }    

 

조금 복잡하긴 하지만 나름 정리를 잘 했다고 생각하고 동작시켰습니다.

결과는..?

시간 초과...

 

정렬(Arrays.sort)가 반복문을 통해서 계속 동작하므로 역시나 "시간초과"라는 결과가 나오고 말았습니다.

개념부분은 전부 통과 되었는데..속도를 개선하기 위한 방법이 필요 하였습니다..

 

* 우선순위 큐(PriorityQueue)

자바에서 우선순위큐는 사용자가 지정한 데이터 형식을 바탕으로 스스로 정렬 해 주는 클래스 입니다.

데이터를 추가(offer)하거나, 꺼내는(poll) 행위를 하면 해당 행위가 끝남과 동시에 데이터가 정렬이 됩니다.

위 개념을 바탕으로 우선순위 큐를 사용하면 정말 이래도되나 싶을 정도로 간단하게 코드를 완성 할 수 있습니다.

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> data = new PriorityQueue();

        for (int aScoville : scoville) {  //1) 우선순위 큐에 넣습니다.
            data.offer(aScoville);
        }
        
        //2) 데이터를 정렬 할 필요가 없습니다. 큐에 넣으면 자료형(T)에 의해 바로 정렬이 됩니다.
        
        while (data.peek() <= K) {  //3) 요구한 스코빌 지수보다 작을 때 까지 반복문을 동작 합니다.
            if (data.size() == 1) {  //4) 더이상 할게 없으면 종료 합니다.
                return -1;
            }
            int first = data.poll();  //5) 첫번째 데이터를 꺼냅니다.
            int second = data.poll();  //6) 두번째 데이터를 꺼냅니다.


            int result = first + (second * 2);  //7) 공식에 의해 데이터를 합칩니다.

            data.offer(result);  //8) 합친 값을 넣어 줍니다.
            answer ++;  //9) 횟수를 증가시킵니다.
        }
        return answer;
    }
}

 

우선순위큐에서 offer 메소드는 데이터를 넣는 메소드 입니다.

데이터가 해당 메소드를 통해서 들어가자마자 바로 정렬이 됩니다.

정렬은 기본적으로 오름차순이며 Collections의 reverseOrder 메소드를 통해서 내림차순으로 변경 할 수 있습니다.

 

peek 메소드는 맨 처음에 존재하는 값 입니다.

poll 메소드도 맨 처음에 존재하는 값을 가져오지만 poll 메소드를 실행하면 우선순위 큐에서 데이터가 제거가 됩니다.

그러므로 원하는 스코빌 지수를 계산방법에 의해 섞으려면 poll메소드를 실행해서 데이터를 변경 한 뒤에 offer 메소드를 통해서 넣어주면 됩니다.

 

단순히 offer와, poll, peek 메소드 3개만으로도 데이터를 정렬 순서에 따라서 관리 할 수 있습니다.

위 코드를 실행하여 보았습니다.

통과했습니다!

 

배열을 가지고 지지고 볶고 난리를 치고 있다가 우선순위 큐를 사용한다는 힌트를 얻고선 허무하게 끝나고 말았습니다..

사실 이진트리를 구현한 다음에 데이터를 변경 및 삭제후 직접 정렬하는 코드를 만들고 있었는데..

이게 좀처럼 쉽지는 않았던 것 같습니다...;ㅁ;

 

이상으로 프로그래머스 힙 첫번째 문제인 더 맵게에 대해서 살펴보았습니다.

궁금하거나 틀린점은 언제든 연락주세요! :)