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

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

---

실패한 코드

/*
1. 스코빌 배열을 정렬한다.
2. 배열을 순회하며 K와 작은 지 비교한다. 크거나 배열의 끝에 다다르면 종료한다.
3. 작을 경우 해당 요소와 바로 다음 요소를 섞는다. 카운트를 1 증가한다.
4. 섞은 값으로 대체하고 정렬 후 순회의 인덱스를 조절한다.
5. 섞은 값이 다시 K 보다 작은 지 비교하며 위 과정을 반복한다.
*/

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        Arrays.sort(scoville);
        for(int i=0; i<scoville.length-1; i++){
            if(scoville[i]>K) continue;
            else {
                int temp = scoville[i] + (scoville[i+1] * 2);
                scoville[i] = -1;
                scoville[i+1] = temp;
                Arrays.sort(scoville);
                answer++;
            }
        }
        return answer;
    }
}

실패한 테스트케이스도 있고 효율성 테스트도 모두 시간초과했다.

힙 이라는 자료구조로 분류가 되어 있었는데 해당 지식이 잘 기억이 안났다 .. 

학습 후에 다시 풀어보았다.

다시 푼 코드

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> heap = new PriorityQueue();

        for (int item : scoville) {
            heap.offer(item);
        }

        while (heap.peek() < K) {
            if (heap.size() == 1) {
                return -1;
            }
            int a = heap.poll();
            int b = heap.poll();

            int result = a + (b * 2);

            heap.offer(result);
            answer ++;
        }
        return answer;
    }
}

 

짧게 정리해두자.

 

우선순위 큐 (자바)

우선순위 큐는 우선순위를 가진 데이터를 먼저 내보내는 큐이다. 루트 노드가 꺼내진다.

일반적으로 Heap으로 구현한다.

최대값이 우선순위인 큐는 Max Heap, 최솟값이 우선순위인 큐는 Min Heap 으로 구현한다.

java.util.PriorityQueue 라는 클래스를 자바에서 제공한다.

우선순위라는 기준은 어떻게 처리될까?

PriorityQueue를 사용하기 위해선 우선순위 큐에 저장할 객체는 필수적으로 Comparable Interface를 구현해야한다.

Comparable Interface를 구현하면 compareTo method를 override 하게 되고 해당 객체에서 처리할 우선순위 조건을 리턴해주면 PriorityQueue 가 알아서 우선순위가 높은 객체를 추출 해준다.

import java.util.PriorityQueue;
import java.util.Collections;

//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();

//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());

 

자세한 내용은 아래 링크에서 공부하자.

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90