[Programmers]-더 맵게(힙)

문제

가장작은 수를 이용하는 쪽에서 heap을 써야하고

거기에 맞는 우선순위 큐를 이용한다.

“코딩테스트 고득점 Kit - 힙(Heap)” 문제이다.

다시 풀어보았다.

코드

import java.util.*;

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

        PriorityQueue<Integer> q = new PriorityQueue<Integer>(); // 객체 선언

        for(int i=0;i<scoville.length;i++){ // 배열로 받은 데이터 큐에 offer
            q.offer(scoville[i]);
        }

        int scov;

        while(q.peek() < K){//K보다 작으면

            if(q.size() == 1) return -1; // 더이상 7이상으로 만들 수 없으면 -1리턴

            scov = q.poll() + (q.poll()*2);

            q.offer(scov);

            answer++;
        }
        return answer;
    }
}

다시푼 코드

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        for(Integer sco : scoville) q.offer(sco);
        
        //새로운 음식 만드는 과정
        int answer = 0;
        while(q.peek() < K){
            if(q.size() < 2) return -1;//더이상 못만들경우
            answer++;
            
            int N = q.poll();
            q.offer(N + q.poll() * 2);
        }
        return answer;
    }
}

요약

• q.offer(data) : 데이터 큐에 넣기
• q.poll() : 최근 데이터 반환, 삭제
• q.peek() : 최근 데이터 반환
• q.size() : 큐의 크기 반환

시간이 좀 단축 되었다.

엄청 달라진 것은 없다.