[프로그래머스] LV.2 더 맵게

[프로그래머스] LV.2 더 맵게

 

1. 문제 : Link

배열을 주고 가장 작은 수가 K보다 크게끔 만들어주는 문제

가장 작은 수와 두 번째로 작은수를 mix하여 큰수를 만들어주는데 이 수가 K보다 작은지 큰지 확인해줘야함

 

2. 풀이

배열과 pop을 이용해서 구현했지만 효율성 테스트에서 떨어짐

heapq를 이용해서 min값을 가져오는 효율을 높임

 

3. 코드

def solution(scoville, K):
    answer = 0
    while 1: 
        p = 0
        if len(scoville) == 1:
            if scoville[0] >= K:
                return answer
            else:
                return -1
        for s in scoville:
            if s < K:
                break
            else:
                p += 1
        if p == len(scoville):
            return answer
        else:  
            scoville.sort()
            new = scoville.pop(0) + (scoville.pop(0) * 2)
            scoville.append(new)
            answer += 1

import heapq
def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)
    
    while scoville[0] < K:
        mix = heapq.heappop(scoville) + (heapq.heappop(scoville) * 2)
        heapq.heappush(scoville, mix)
        answer += 1
        if len(scoville) == 1 and scoville[0] < K:
            return -1
    return answer

import java.util.*;

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

        // priority queue 생성
        for (int i : scoville) {
            pq.add(i);
        }

        while (true) {
            // 최소치를 넘은 경우 종료
            if (pq.peek() >= K) break;
			
            // 더 이상 섞을 수 없는 경우 -1 후 종료
            if (pq.size() == 1) {
                answer = -1;
                break;
            }
            
            // 2개를 뽑아 섞고 다시 삽입
            pq.add(pq.poll() + pq.poll() * 2);
            answer++;
        }
        
        return answer;
    }
}