[알고리즘 문제 풀이] 프로그래머스 - 더 맵게

문제 원본 링크: https://programmers.co.kr/learn/courses/30/lessons/42626

카테고리: 힙(Heap)

 

문제 설명

모든 음식의 스코빌 지수를 K 이상으로 만드려고 한다. 그러기 위해서는 스코빌 지수가 가장 낮은 두 개의 음식을 다음과 같은 방법으로 섞어 새로운 음식을 만든다. 

// 새로운 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수  그 다음으로 가장 맵지 않은 음식의 스코빌 지수 * 2

그리고 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return하도록 solution 함수를 작성하라.

 

제한 사항

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

 

입출력 예

int[] scoville = {1,2,3,9,10,12};
int k = 7; // answer = 2

 

내 풀이

1. scoville 값을 PrioritiyQueue queue에 넣는다.
2. queue의 값에 K 이하인 값이 있는지 확인한다.
3. 있으면 가장 맵지 않은 두 값을 섞고 answer ++
4. 없으면 answer를 리턴한다.
5. 2~3번을 K이하인 값이 없을 때까지 혹은 queue에 값이 하나가 남을 때까지 반복한다.
6. queue에 남은 값이 하나이고 K 보다 작다면 -1을 리턴한다.

PriorityQueue를 사용하면 쉽게 풀 수 있다. PriorityQueue의 사용법은 Queue와 동일하지만 내부적으로는 힙구조를 가지고 있어서 정렬된 순서로 값을 꺼낼 수 있다. 나는 오름차순을 사용했지만 Collections.reverseOrder를 사용해 내림차순도 가능하다.

자바 코드

    public int solution(int[] scoville, int K) {
        int answer = 0;

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int s : scoville) queue.offer(s);

        while (true) {
            boolean hasSmallerThanK = false;

            // k보다 작은수가 있는지 확인, 있으면 for문 종료
            for (int value : queue) {
                if (value < K) {
                    hasSmallerThanK = true;
                    break;
                }
            }

            if (hasSmallerThanK) {
                // queue에 남은 값이 2개 이상이면 섞기
                if (queue.size() >= 2) {
                    queue.offer(queue.poll() + (queue.poll() * 2));
                    answer++;

                // queue에 남은 값이 1개이고 k보다 작다면 -1 리턴
                } else {
                    return -1;
                }

            // queue에 남은 값중에 k보다 작은 값이 없다면 answer리턴
            } else {
                return answer;
            }
        }
    }

 

채점 결과

 

 

다른 사람의 풀이

    public int solution3(int[] scoville, int K) {
        PriorityQueue<Integer> pqScov = new PriorityQueue<>();
        for (int s: scoville) {
            pqScov.add(s);
        }

        int cnt = 0;
        while (pqScov.size() > 1 && pqScov.peek() < K) {
            pqScov.add(pqScov.remove() + pqScov.remove() * 2);
            cnt++;
        }

        return pqScov.peek() >= K ? cnt : -1;
    }

같은 방식의 풀이지만 훨씬 간결하게 작성할 수 있었다. 

 

참고

- 깃허브 소스코드: 링크