[문제풀이] Level2 더 맵게

더 맵게

---

  🪅 매번 배열의 원소를 제거하고 넣고, 정렬해야하는 조건에서 우선순위 큐를 생각해 낼 수 있느냐
  🪅 같은 동작을 반복해서 해야할 때 이를 메서드로써 만들 수 있느냐
  🪅 항상 처음과 끝은 예외상황이 발생할 수 있는 것을 확인했느냐

💡 문제 접근 과정
음식 개수에 따라 scoville 최초 배열의 길이가 달라지고
한 번 스코빌 지수를 섞을 때마다, 배열의 길이가 1씩 줄어든다.
이 조건을 봤을 때 가변길이 배열(ArrayList)을 써야겠다는 생각이 들었다.
이 자료구조를 썼더니 매번 정렬해줘야돼서인지(?) 효율성테스트를 통과하지 못했다.
(중간에 모든!! 음식의 스코빌 지수가 K이상이어야하는 조건을 놓쳐서 많이 헤맸다)

즉, 자료구조에 원소를 넣을 때마다 정렬을 해주는 자료구조가 무엇인지 생각해봤고, 우선순위 큐가 알맞는다고 생각했다
문제의 조건처럼, 가장 낮은 수(스코빌지수) 두 개를 우선순위 큐에서 빼내고 섞어서 다시 우선순위 큐에 넣고,
가장 낮은 숫자가 K 이상인지 확인하는 과정을 거쳤다.

[일부 성공, 효율성테스트를 통과하지 못한 코드.java]

import java.util.*;

class Solution {
    int mixCnt = 0;
    int answer = 0;
    boolean isSatisfied = false;
    public int[] mix(int[] scoville, int K) {
        List<Integer> list = new ArrayList<>();

        Arrays.sort(scoville);
        int first = scoville[0];
        int second = scoville[1];
        int m = first + 2*second;
        mixCnt++;
        if(m >= K) {
            answer = mixCnt;
            isSatisfied = true;
        }
        list.add(m);
        for(int i = 2; i < scoville.length; i++) {
            list.add(scoville[i]);
        }
        Integer[] arrWrapper = list.toArray(new Integer[0]);
        scoville = Arrays.stream(arrWrapper).mapToInt(Integer::intValue).toArray();
        return scoville;
    }

    public int solution(int[] scoville, int K) {
        for(int i = 0; i < scoville.length-1; i++) {
            // for(int j = 0; j < scoville.length; j++) {
            //     System.out.print(scoville[j] + " ");
            // }
            // System.out.println();
            if(isSatisfied == true) break;
            scoville = mix(scoville, K);
        }

        if(isSatisfied == false) return -1;

        return answer;
    }
}

[성공, 효율성테스트를 통과한 코드.java]

import java.util.*;

class Solution {
    int mixCnt = 0;
    int answer = 0;
    boolean isSatisfied = false;
    public Queue<Integer> mix(Queue<Integer> pQueue, int K) {
        int first = pQueue.poll();
        int second = pQueue.poll();
        int m = first + 2*second;

        mixCnt++;
        pQueue.add(m);
        int min = pQueue.peek();
        if(min >= K) {
            answer = mixCnt;
            isSatisfied = true;
        }
        return pQueue;
    }

    public int solution(int[] scoville, int K) {
        Queue<Integer> pQueue = new PriorityQueue<>();

        // pQueue 초기화
        for(int i = 0; i < scoville.length; i++) {
            pQueue.add(scoville[i]);
        }

        int min = pQueue.peek();

        // 애초부터 모든 음식의 스코빌지수가 K이상일 수 있다
        if(min >= K) {
            return 0;    
        }

        for(int i = 0; i < scoville.length-1; i++) {
            if(isSatisfied == true) break;
            pQueue = mix(pQueue, K);
        }

        if(isSatisfied == false) return -1;
        return answer;
    }
}

🎁 배열이 정렬되어있으면 중첩for문을 쓰지 않고도 문제를 해결할 수 있다