[프로그래머스] [힙(Heap)] 더 맵게

문제

프로그래머스 > 코딩테스트 연습 > 힙(Heap) > 더 맵게

 

언어

JAVA

 

난이도 

Lv.2

 

풀이시간 

2시간

 

문제 풀이

1. PriorityQueue 사용하여 데이터를 삽입, 제거한다.

※주의 : ArrayList 를 사용할 경우 시간 초과로 불합격 된다.

 

소스코드

import java.util.*;
 
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        // Min 값으로 자동 Sort해주는 Queue 라이브러리 
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
        // 배열을 힙으로 만든다.
        for(int i = 0; i < scoville.length; i++) {
            heap.offer(scoville[i]);
        }
        
        while (heap.peek() <= K) {
            // K 스코질 비수 미만 음식 1개라도 있으면 -1 반환 
            if(heap.size() == 1 ) {
                answer = -1;
                break;
            }
    
            // poll 하는 순간 큐에서 제거된다.
            // 스코빌 지수 가장 낮은 음식
            int low1 = heap.poll();
            // 스코빌 지수 두번째 낮은 음식
            int low2 = heap.poll();
            
            // 스코빌 지수 섞은 음식
            int mix = low1 + (low2 * 2);
            
            heap.offer(mix);
            answer ++;
        }
        return answer;
    }    
}

불합격 소스코드 (시간 초과)

import java.util.*;
 
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        // 테스트했던 이클립스 환경이 java 1.8 버전이라 단순하게 for문으로 ArraList 변환 작업
        // 배열 파싱 정보인 commands 배열 수만큼 리스트를 초기화 해야 한다.
        List<Integer> arrayList = new ArrayList<Integer>();
        for (int i = 0; i < scoville.length; i++) {
            arrayList.add(scoville[i]);
        }
        
        int mixCnt = 0;
        while(arrayList.size() > 1) {
            arrayList.sort(null);
            // 스코빌 지수 가장 낮은 음식
            int low1 = arrayList.get(0);
            // 스코빌 지수 두번째 낮은 음식
            int low2 = arrayList.get(1);
            // 스코빌 지수 섞은 음식
            int mix = low1 + (low2 * 2);
            
            arrayList.remove(0);
            arrayList.remove(0);
            arrayList.add(mix);
            // 섞은 횟수 +1
            mixCnt++;
            // 모든 음식의 스코빌 지수가 K 이상인지 체크
            if(checkScoville(arrayList, K) == true) {
                break;
            }
        }
        
        // 섞은 횟수 return
        // 모든 음식의 스코빌 지수가 K 이상이 안되는 경우 -1 return
        if(checkScoville(arrayList, K)) {
            answer = mixCnt;
        } else {
            answer = -1;
        }
        
        return answer;
    }
    
    public static boolean checkScoville(List<Integer> arrayList, int K) {
        boolean flag = true;
        for (int i = 0; i < arrayList.size(); i++) {
            // 모든 음식 스코질 지수 K 이상 유무 체크
            // 한가지 음식이라도 K 미만일 경우 false 반환
            if(K > arrayList.get(i)) {
                flag = false;
                break;
            }
        }
        return flag;
    }
}

 

후기

정답 테스트는 통과했으나 효율성에서 불합격 됐다.ArrayList 대신 PriorityQueue를 사용했어야 했다. 

PriorityQueue를 사용해본 적이 없어 당황했다. 

실력, 경험, 센스 부족을 절실히 느낀다.

 

출처

프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 

https://jar100.tistory.com/18