[프로그래머스] 더 맵게

※ 해당 문제의 링크는 여기입니다. ※

프로그래머스에서 설명되어 있듯이 "힙을 이용해서 우선순위 큐를 구현할 수 있습니다." 라고 설명되었있습니다.

우선순위 큐와 힙에 대해서 궁금하신 분들은 링크 참조해주세요.

 

제한사항

1. 스코빌의 길이는 2이상 1000000 입니다.
2. K는 0이상 1000000000 입니다.
3. 스코빌의 원소는 각각 0이상 1000000 입니다.
4. 모든 음식의 스코빌 지수를 K이상으로 만들 수 없다면 -1를 반환합니다.

문제는 레벨 2 치곤 꽤 쉬운 편입니다.

(레벨 1에서 이상한 문제를 만난 적이 있어서 일종의 트라우마가 생겨버린 것 같기도;;)

 

그리고 효율성 테스트까지 있기때문에 시간복잡도도 적당히 꼬아야합니다.

(재귀함수를 사용해서는 효율성 테스트를 통과하기 어렵다는 의미입니다.)

 

알고리즘

먼저, 가장 스코필이 낮은. 즉, 가장 맵지 않은 음식과 2번째로 맵지 않은 음식을 섞어서 

새롭게 매운 음식을 만들어야합니다.

(도대체 왜..?)

그렇기 위해서는 배열을 사용할 수도 있을 것이고, 우선순위 큐와 힙을 사용해서 해결할 수 있을 겁니다.

또는 Inner Class를 사용해서 문제를 해결할 수도 있을 겁니다.

하지만, 배열을 이용한다면, 시간이 굉장히 많이 소모가 될 것입니다.

새로운 음식을 만들때마다 계속 정렬을 해주어야하니, 그만큼 시간이 더 소모될 것입니다.

그래서, 저같은 경우에는 우선순위 큐를 사용해서 문제를 해결하였습니다.

 

if (scovilles.isEmpty() || scovilles.size() == 1) {
    return -1;
}

먼저, 스코빌 큐가 비어 있거나, 길이가 1인지를 판단합니다.

더 이상 음식을 만들 수도 없기때문에 -1를 반환합니다.

int notSpicy = scovilles.poll();

그리곤 가장 맵지 않은 음식을 poll로 삭제 및 반환해서 가져옵니다.

int lessSpicy = 0;
if (!scovilles.isEmpty()) {
    lessSpicy= scovilles.poll();
}

2번째로 맵지 않은 음식을 Null-Safe하게 가져오기 위해

굉장히 비효율적으로 스코빌 큐가 비었는 지를 다시 한 번 더 확인한 후 삭제 및 반환해서 가져옵니다.

scovilles.add(notSpicy + (lessSpicy * 2));
result++;

가장 맵지 않은 음식의 스코빌과 2번째로 맵지않은 음식의 스코빌을 알았으니,

문제에서 설명해준 공식에 대입한 결과를 스코빌 큐에 넣습니다.

그 후, 총 몇 번이나 소모되었는 지를 최종적으로 반환하라고 하였으므로 result +1를 해줍니다.

overK = isOverThan(scovilles, k);

overK 변수에 꾸준히 스코빌 큐와 k 값으로 모든 스코빌의 값들이 k보다 높은 지 판단하도록 하였습니다.

public boolean isOverThan(Queue<Integer> queue, int k) {
    for (int i : queue) {
        if (i < k) {
            return false;
        }
    }

    return true;
}

전체 소스코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int k) {
        // 1. 정렬
        // 2. 가장 낮은 거 2개씩 계산한다.
        // 3. k보다 높으면 중단

        Queue<Integer> scovilles = new PriorityQueue<>(); // 우선순위 큐
        for (int s : scoville) {
            scovilles.add(s);
        }
        boolean overK = false;
        int result = 0;

        while (!overK) {
            if (scovilles.isEmpty() || scovilles.size() == 1) {
                return -1;
            }

            int notSpicy = scovilles.poll();
            int lessSpicy = 0;
            if (!scovilles.isEmpty()) {
                lessSpicy= scovilles.poll();
            }

            scovilles.add(notSpicy + (lessSpicy * 2));
            result++;

            // 평균값이 k 이상이면 됨
            overK = isOverThan(scovilles, k);
        }

        return result;
    }

    public boolean isOverThan(Queue<Integer> queue, int k) {
        for (int i : queue) {
            if (i < k) {
                return false;
            }
        }

        return true;
    }
}

추가로

코드가 매우 단순합니다.

물론 굉장히 비효율적입니다.

다른 분들이 푸신 방법으로 효율성 테스트를 해본 결과 제 자신이 매우 부끄러워지더군요

(무려 제가 1800ms나 걸렸던 효율성 테스트를 1600ms 밖에 걸리지않더군요;;)

 

 

이상입니다.