더_맵게.md

더 맵게

문제 링크

문제 설명

모든 음식의 스코빌 지수를 K 이상으로 만들려고한다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해서는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만들어야 한다.
섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해라.

문제 풀이

1. Java 풀이
   전형적인 priorityQueue / heap 문제이다. PriorityQueue를 오름차순으로 정렬되게 한 후(기본설정, 내림차순으로 정렬할 시 Collections.reverseOrder() 매개변수로 전달) 주어진 scoville 배열을 PriorityQueue에 넣은 후 while문으로 가장 낮은 scoville의 값이 K이상이 나올때까지 반복한다. 반복문 안에서 2개의 최소 값을 꺼내고 계산하여 다시 PriorityQueue에 add 한다.

2. JavaScript 풀이
   전형적인 Heap 문제이다. 배열의 shift()연산을 통해 큐 연산을 해준다. 주어진 scoville배열을 오름차순 정렬해 준 후 while문으로 가장 낮은 scoville의 값이 K이상이 나올때까지 반복한다. 반복문 안에서 2개의 최소 값을 꺼내고 계산하여 다시 배열에 push() 한다. 매 push시마다 배열정렬을 다시해줘야 한다.

풀이코드 Java

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        int answer = 0;
        for( int aScoville : scoville){
            priorityQueue.offer(aScoville);
        }
        while(priorityQueue.peek() < K){
            if(priorityQueue.size() == 1 ) return -1;
            answer++;
            int first = priorityQueue.poll();
            int second = priorityQueue.poll();
            int newSocvile = first + ( second * 2 );
            priorityQueue.offer(newSocvile);
        }
        return answer;
    }
}

풀이 코드 JavaScript

• 해당문제는 자바스크립트 채점을 지원 안함. 테스트 코드 통과

function solution(scoville, K) {
  if (scoville.length == 0) return -1;
  let answer = 0;
  while (scoville[0] < K) {
    if (scoville.length == 1) return -1;
    answer++;
    const first = scoville.shift();
    const second = scoville.shift();
    const newSocvile = first + second * 2;
    scoville.push(newSocvile);
  }
  return answer;
}