[프로그래머스] 더 맵게 - Java, Python

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=python3

우선순위 큐를 사용하여 풀이할 수 있는 문제입니다.

문제 조건을 꼼꼼히 살피지 않아서 런타임 에러가 발생했었는데, 문제 조건에 scoville의 길이는 2이상 1,000,000 이하 인 것과, 모든 음식의 스코빌 지수가 K 이상이 되지 않을 경우에는 -1을 return 해야 한다는 것을 코드로 나타내 주어야 합니다.

 

파이썬은 heapq 모듈을 사용하여 우선순위 큐를 구현하였으며, priorityQueue 보다 시간 복잡도 측면에서 훨씬 빠르기 때문에 heapq 모듈을 사용하는 것이 좋을 것 같습니다.

 

자바의 경우, poll() 메서드와 peek() 메서드를 활용하여 문제를 해결할 수 있었습니다.

[Python]

import heapq

def solution(scoville, K):
    answer=0
    
    #우선순위 큐 생성 -> 기존의 리스트를 힙 자료구조로 변경
    heapq.heapify(scoville)
    
    # k보다 작을 동안 스코빌 지수를 갱신해줌
    while scoville[0] < K and len(scoville) > 1:
        heapq.heappush(scoville, heapq.heappop(scoville) + heapq.heappop(scoville) * 2)
        answer+=1
    return answer if scoville[0] >= K else -1

[Java]

import java.util.*;

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

        for (int s : scoville) {
            pq.add(s);
        }

        while (pq.peek() <= K) {
            if (pq.size() == 1) {
                return -1;
            }
            pq.add(pq.poll() + pq.poll() * 2);
            answer += 1;
        }
        return answer;
    }
}