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

코딩 실력을 기르기 위해 프로그래머스와 백준을 통해 알고리즘 문제를 풀이한 과정을 기록한다.

더 맵게 : 힙(Heap) 알고리즘

개인 노션 링크

문제 원본 링크

---

[문제 설명]

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다.

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

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

이 과정을 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다.

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

[입출력 예]

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회입니다.

---

풀이 과정

• 첫번째 접근 : 배열 리스트로 구현
  • 정확성 테스트는 모두 통과하지만, 효율성 테스트에서 시간 초과가 발생
  • 이는 가장 작은 두 숫자를 찾는 과정에서 문제가 발생하는 것
  • Collection.sort()를 통한 정렬 과정이 필요

import java.util.ArrayList;
import java.util.List;

class Solution {
    static int count = 0; //섞은 횟수
    static int firstIndex = 0, secondIndex = 0; //첫째, 둘째로 작은 수의 인덱스
    static List<Integer> heap = new ArrayList<>();

    public int solution(int[] scoville, int K) {
        arrayToList(heap, scoville); //잦은 삭제와 추가로 인해 리스트를 이용

        while (!isBiggerK(heap, K)) { //K보다 작은 값이 없을때까지 반복
            if (heap.size() < 2) return -1;
            makeSpicy(heap);          //맵게 만들기
        }

        int answer = count;
        return answer;
    }

    public void arrayToList(final List list, final int[] array) { //배열을 리스트로 복사
        for (int i = 0; i < array.length; i++) {
            int a = array[i];

            list.add(a);
        }
    }

    public boolean isBiggerK(final List list, final int K) {
        boolean isBigger = true; //초기값은 모두 K보다 크다고 가정

        for (int i = 0; i < list.size(); i++) {
            int temp = (int) list.get(i);

            if (temp < K) {
                isBigger = false; //K보다 작은 값이 있으면 false
                break;
            }
        }
        return isBigger;
    }

    public void makeSpicy(final List list) {
        chooseSmall(list); //가장 작은 수와 두번째로 작은 수의 인덱스를 알아옴

        int a = (int) list.get(firstIndex);
        int b = (int) list.get(secondIndex);
        int c = a + 2 * b;

        list.add(c);
        list.remove(firstIndex);
        list.remove(secondIndex);
        count++;
    }

    public void chooseSmall(final List list) {
        int tempFirst = (int) list.get(0);
        int tempSecond = (int) list.get(0);

        for (int i = 1; i < list.size(); i++) {
            if (tempFirst >= (int) list.get(i)) {
                tempFirst = (int) list.get(i);
                firstIndex = i;
            }
        }

        for (int i = 0; i < list.size(); i++) {
            if (tempSecond >= (int) list.get(i) && tempFirst < (int) list.get(i)) {
                tempSecond = (int) list.get(i);
                secondIndex = i;
            }
        }
    }
}

• 두번째 접근 : 우선순위 큐를 이용해 구현
  • 오름차순 정렬이 기본으로 적용되기 때문에 정렬에 시간을 들이지 않음
  • 또한 작은 수를 고르는 과정이 필요 없어져 코드가 간결해짐

package moreSpicy;

import java.util.PriorityQueue;

class Solution2 {
    static int count = 0; //섞은 횟수
    static PriorityQueue<Integer> heap = new PriorityQueue<>();

    public int solution(int[] scoville, int K) {
        arrayToQueue(heap, scoville); //잦은 삭제와 추가로 인해 리스트를 이용

        while (heap.peek() < K) { //K보다 작은 값이 없을때까지 반복
            if (heap.size() < 2) return -1; //K 이상으로 만들 수 없는 경우
            makeSpicy(heap);          //맵게 만들기
        }

        int answer = count;
        return answer;
    }

    public static void arrayToQueue(final PriorityQueue queue, final int[] array) { //배열을 리스트로 복사
        for (int a : array) {
            queue.add(a);
        }
    }

    public static void makeSpicy(final PriorityQueue queue) {
        int a = (int) queue.poll();
        int b = (int) queue.poll();
        int c = a + 2 * b;

        queue.add(c);
        count++;
    }
}