[프로그래머스] 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626?language=java 

코딩테스트 연습 - 더 맵게

힙을 활용한 문제 접근 필요

우선순위 큐 사용하였음.

public int solution(int[] scoville, int K) {
        int returnValue = 0;
        
        // 우선순위 큐 선언
        Queue<Integer> queue = new PriorityQueue<>();
        
        // int 형태를 Integer로 전환(람다를 만약 쓴다면...)
        //List<Integer> convertArray = Arrays.stream(scoville).boxed().collect(Collectors.toList());
        //queue.addAll(convertArray);
        
        // int 형태를 Integer로 전환(람다 안쓰면 효율성 개선됨)
        for(int i = 0; i < scoville.length; i++) {
            queue.add(scoville[i]);
        }
        
        // 큐에 값이 있을 동안 값을 뽑아냄
        while(!queue.isEmpty()) {
            int firstValue = queue.poll();
            if(firstValue < K) {
                int secondValue = queue.poll();
                int mixValue = firstValue + (secondValue * 2);
                
                // 조합한 값이 K보다 작은데 다음값이 없을 경우 -1 반환
                if(mixValue < K && queue.isEmpty()) {
                    queue.clear();
                    returnValue = -1;
                } else { // 그게 아닐 경우 믹스값 더해줌
                    queue.add(mixValue);
                    returnValue++;
                }
            } else {
                queue.clear();
            }
        }
        return returnValue;
    }

람다로 queue에 담을 경우

 

heap 참고링크

https://shanepark.tistory.com/261

JAVA로 알아보는 힙 (Heap) 자료구조

https://st-lab.tistory.com/225

자바 [JAVA] - 힙 정렬 (Heap Sort)