[프로그래머스] 더 맵게 - JAVA

문제 설명

알고리즘 자체는 어렵지 않았다.
'배열을 오름차순으로 정렬 후 맨 앞의 값과 그 다음 값을 생각하며 스코빌 지수(K)와 비교하면 되겠다!'

그런데 제한 사항에 있는 어마어마한 배열 길이를 보고 '단순 정렬을 하면 너무 오래 걸리겠구나'라는 판단을 했다.

그래서 자바의 배열 종류를 찾아보니 자동으로 추가한 값을 정리해 주는 PriorityQueue를 발견했다.

최초 통과 코드

import java.util.*;

class Calc{
	// 짜 놓은 코드가 2번 이상 식을 사용하기에 method로 만들어줬다.
    public static Integer hotSum(int min1, int min2) {
        return min1 + (min2 * 2);
    }
}

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        // 짱짱 queue를 만들어준다. 기본적으로 안에 있는 값을 오름차순으로 정렬해준다.
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int i=0;i<scoville.length;i++){
            pq.add(scoville[i]);
        }
        // 정렬된 queue의 첫 값과 그 다음 값을 추출한다.
        int min1 = pq.poll();
        int min2 = pq.poll();
        
        while(min1 < K){
        	// 이 반복문에 들어왔다는 것은 연산이 무조건 한 번 이상 시행될 것이라는 뜻이므로(answer++)
            answer++;
            // queue에 연산 값을 추가한다.
            pq.add(Calc.hotSum(min1, min2));
            // 자동으로 정렬이 됐으므로 그 다음 최솟값을 뽑는다.
            min1 = pq.poll();
            // 최솟값이 K보다 크면 바로 답을 반환
            if(min1 > K) return answer;
            // 그렇지 않으면 두 번째 값도 추출한다.
            min2 = pq.poll();
            // 그 후 queue가 비어있다면 마지막 연산이라는 뜻이므로
            if(pq.isEmpty()) {
            	// 그 결과를 반환해준다.
                return calc.hotSum(min1, min2) > K ? ++answer : -1;
            }
        }
        return -1;
    }
}

코드가 예상외로 빨리 통과가 돼서 중복되는 감이 있는 코드(min < K, min > K..)들이 있다.
그리고 조금 더 찾아봤는데 queue에는 첫 번째 값을 뽑아주는 poll만 있는 줄 알았는데, 첫 번째 값을 추출하지 않고 값만 가져오는 peek메서드도 있었다...(눈물 줄줄)

언어를 익힐 때, 조금 빨리 익혀보려고 코딩테스트로 공부하는 편인데... 이래서 야매 코딩은 무섭다. peek메서드를 안 이상 이렇게 넘어갈 순 없어서 코드를 다시 짜고 정리해봤다.

최종 코드

import java.util.*;

class Calc{
    public static Integer hotSum(int min1, int min2){
        return min1 + (min2 * 2);
    }
}

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int i=0;i<scoville.length;i++){
            pq.add(scoville[i]);
        }
        // 처음과 달리 queue를 변경하지 않고 첫 번째 값만 가져올 수 있어 조건을 바꿨다.
        // queue가 비어 있을 경우 값을 추출하면 error가 나기에
        // isEmpty() 보다는 queue.size가 1이 되면 탈출하게끔 추가해줬다.
        while(pq.peek() < K && pq.size() > 1){
            answer++;
            // 구현한 메소드에 최솟값, 그 다음 값을 넣어 연산후 queue에 추가해준다.
            pq.add(Calc.hotSum(pq.poll(), pq.poll()));
        }
        // 최종 값이 K보다 크면 answer를 아니면 -1을 반환한다.
        return pq.peek() > K ? answer : -1;
    }
}

peek메서드를 이용하니 처음 코드보다 훨씬 간결해졌다..! 역시 아는 것이 힘이다.😆