99클럽 코테 스터디 5일차 TIL - LV2. 더 맵게

 

오늘의 학습 키워드

• 힙(Heap)

오늘의 회고

1. 문제

문제 URL

프로그래머스

2. 해결 방안

<직접 짠 코드> 통과는 했으나 개선 필요

public int solution1(int[] scoville, int K) {
    int answer = 0;

    // 1. 우선순위큐 요소 넣기 (최소힙)
    PriorityQueue<Integer> minQueue = new PriorityQueue<>();
    for(int i=0; i<scoville.length; i++) {
        minQueue.add(scoville[i]);
    }

    // 2. 힙에 값이 없을 때 까지 반복
    while(!minQueue.isEmpty()) {
        if(minQueue.peek() >= K) { // 2-1. 요소가 K 이상이면 뺀다 (안섞음)
            minQueue.poll();
        }else {                     // 2-2. 요소가 K 미만이면
            // 2-2-1. 요소 1개라면, return -1
            if(minQueue.size() < 2) return -1;
            else {
                // 2-2-2. 최소 2개라면, 섞고 횟수+1
                minQueue.add(minQueue.poll() + (minQueue.poll() * 2));
                answer++;
            }
        }
    }

    return answer;
}

• 우선순위 큐로 최소힙을 만들어서 가장 작은 값(큐의 첫번째 요소)을 뽑아낸다.
• 나머지는 요구 사항에 맞는 필요 로직을 짜주면 된다.
• 개선점 : 여기서는 큐에 값이 남아있지 않도록 구현했는데 어차피 항상 최소값이 먼저 뽑히고 그 값만 체크하면 되기 때문에 요소가 K 이상이면 poll 뺄 필요가 없었다.

<개선>

    public int solution2(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> p = new PriorityQueue<>();

        for(int i=0; i<scoville.length; i++) {
            p.add(scoville[i]);
        }

        while(p.peek() < K && p.size() > 1) {
            int newScov = p.poll() + (p.poll() * 2);
            p.add(newScov);
            answer++;
        }

        if(p.peek() < K) return -1;

        return answer;
    }

• 직접 짠 코드는 if 문이 다소 난잡한데 개선 코드에서는 조금 더 깔끔하게 구현할 수 있다.
• 위 개선점도 해결 가능.

3. 피드백

• 그새 힙을 잊어먹어서 틈새 알고리즘 공부 호다닥 하고 구현해보았다.
• 힙을 활용하는 것은 어렵지 않았으나 더 나이스한 방법으로 짜는 것은 계속 하면서 늘려야겠다.