[프로그래머스/Java] 42626번 - 더 맵게

문제 & 난이도

• 우선순위 큐
• 난이도 : 레벨 2

 

풀이

package sorting;

import java.util.PriorityQueue;

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

        //우선순위 큐
        PriorityQueue<Integer> pq = new PriorityQueue<>();

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

        while(pq.peek()<K){
            if(pq.size()<2){
                return -1;
            }

            int first = pq.poll();
            int second = pq.poll();
            int newScoville = first + second*2;
            pq.add(newScoville);

            answer++;
        }
        return answer;
    }
}

 

 

알게된 것 & 느낀 점

 

이번 코딩테스트 스터디 주차 주제가 "정렬"이라 Arrays를 사용해서 풀어야지 하고 정렬을 계속해서 시킨 뒤, 사용한 값을 스코빌 지수로 설정한 값으로 변환하는 알고리즘으로 풀었는데 (아래 코드 참조)

import java.util.Arrays;

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

        //첫 오름차순 정렬
        Arrays.sort(scoville);

        while(scoville[0]<K){
            scoville[0] = scoville[0]+scoville[1]*2;
            scoville[1] = K;
            answer++;
            Arrays.sort(scoville);
        }

        return answer;
    }
}

 

일단 Arrays 계속해서 호출하는 것부터 성능이 크게 저하되는 원인이라고 한다. 

우선순위 큐를 사용하게 되면 내가 사용한 알고리즘을 그대로 사용하되, 정렬을 자동으로 해주는 구조로 장점만을 가지고 있다.

또, 나는 answer 즉 결과만 제대로 출력되면 된다는 생각에 내 맘대로 배열의 값을 K로 바꿨는데 해당 값은 사라진 값으로, 대체되거나 제거되어야 하므로 배열을 수정해서는 안된다고 한다.

정렬을 공부하기로한 주차라 다른 생각은 배제해 두고 정렬에 집중했는데, 한 주제에 치우치지 말고 여러 방면으로 생각해 보자.