[프로그래머스] 더 맵게 -Java(자바)

 

 

 

[프로그래머스] 힙 - 더 맵게-Java(자바)

[문제설명]
매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.
Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

[제한사항]
  - scoville의 길이는 2 이상 1,000,000 이하입니다.
  - K는 0 이상 1,000,000,000 이하입니다.
  - scoville의 원소는 각각 0 이상 1,000,000 이하입니다.
  - 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

[입출력 예]

scoville	K	return
[1, 2, 3, 9, 10, 12]	7	2

[입출력 예 설명]

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

 

 

 

[나의 풀이]

    - 처음에 그냥 List를 썼다가 효율성 문제로 통과 못할뻔했다.

    - PriorityQueue라는 자료구조가 있는데 이것을 사용해야 효율성 문제를 통과할 수 있었다고 한다.

import java.util.PriorityQueue;


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

       PriorityQueue<Integer> heap = new PriorityQueue<>();
       // 1. 제공받은 scoville은 배열이므로 priorityqueue에 음식(요소) 넣기
       for(int i=0; i<scoville.length; i++){
           heap.offer(scoville[i]);
       }

       while(heap.peek() < K){ // 2. 음식맵기지수가 K보다 작으면 실행.
           if(heap.size() < 2) return -1; // 2-1. 비교할거리가 없으면 -1 리턴.
           int f1 = heap.poll(); // 3. 맨앞의 요소(0번째) 삭제(poll)하고 fl변수에 반환
           int f2 = heap.poll(); 
           // 3. 맨앞의 요소(0이삭제되었으니 한칸씩 앞으로) 삭제(poll)하고 f2변수에 반환

           int sco = f1 + (f2 * 2); // 4.반환받은 두 수 스코빌지수 계산.
           heap.offer(sco); // 5.priorityQueue에 나온 값 넣기
           answer++; // 실행할때마다 answer증가.
       }

       return answer;
    }
}

 

[PriorityQueue<>]

    - 우선순위 큐 클래스

    - 우선순위를 먼저 결정하고, 그 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조이다.

    - 내부구조가 힙으로 구성되었기 때문에 시간 복잡도가 O(NLogN)

 

* 선언방법

//  [낮은 숫자부터-오름차순]
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

//  [높은 숫자부터-내림차순]
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());

* 다루는 명령어

    - .peek( ) : get( )과 같은 기능.

    - .poll( ) : remove( )와 같은 기능

    - .offer( ) : add( )와 같은 기능

 

 

[남의 풀이]

    - 간결해서 가져와봤다. return값에 삼항연산자로 표현할수도 있었다.

public int NamEuiGut (int[] scoville, int K) {
        PriorityQueue<Integer> pqScov = new PriorityQueue<>();
        for (int s: scoville) {
            pqScov.add(s);
        }

        int cnt = 0;
        while (pqScov.size() > 1 && pqScov.peek() < K) { 
        // pq가 1보다 크고, K보다 작아야 실행.
            pqScov.add(pqScov.remove() + pqScov.remove() * 2);
            cnt++;
        }

        return pqScov.peek() >= K ? cnt : -1; 
   }