99클럽 코테 스터디 5일차 TIL + 힙(더 맵게)

오늘의 과제

프로그래머스 Lv.2 힙으로 분류된 더 맵게 문제 입니다.

 

다양한 문제에 앞서 많이 쓰이는 자료구조에 대한 이해도를 높이기 위해 선정된 것 같습니다.

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

 

지문이 실생활에 빗대어 있긴 하지만 조금 더 쉬운 이해를 위해 아래와 같이 요구사항을 정리할 수 있습니다.

 

• 주어진 정수 배열의 인자들이 모두 K값 이상이어야 한다.
• K값보다 작은 인자는 가장 작은값 + (두 번째로 가장 작은 값 * 2) 로 섞을 수 있다.
• 모든 인자를 K값 이상으로 만들 수 없다면 -1을 리턴한다.

 

단, 유의할 점이 이전의 문제와는 다르게 입력이 다소 빡빡하게 주어졌습니다.

 

 

처음 접근으로는 가장 작은 값 + 두 번째로 가장 작은 값을 합쳐 K값 이상이 되어야 한다에 꽃혀서

가장 단순히 생각할 수 있는 Sort 후 앞의 값부터 처리하며 올라가는 방법으로 설계했습니다.

 

역시 설계를 글로 적고보니 Sort를 하더라도 매번 합쳐진 값을 다시 정렬해야 하는 상황이 발생하게 되는데

이는 최악의 경우 시간 초과가 발생하게 됩니다.

 

그래서 다시 기본 방법인 문제의 힌트 "힙"에 집중했습니다.

 

문제에서 가장 작은 두 값을 합쳐 값을 만들어 낸다 라는 키워드에서 최소 힙을 떠올렸고

값이 입력될 때 마다 조건에 의해 정렬되는 우선순위 큐를 찾았습니다.

 

이제 걱정거리였던 가장 작은 두 수의 계산을 해결했으니 문제의 조건을 확인만 하면 됩니다.

 

주어진 스코빌 지수 배열을 그저 우선순위 큐에 넣기만 하면 정렬 부분은 끝났고,

이후 계속 합치고 넣고를 반복하며 큐의 사이즈만 신경쓰며 최소 값이 K 이상을 충족하는지

확인해주면 됩니다.

 

아래는 코드 입니다.

import java.util.*;

// 1. 가장 작은 수를 계속 꺼내야 하니 최소 힙.
// 2. 우선순위 큐를 활용
// 3. 꺼낸 값이 최소 스코빌보다 낮다면 mix, cnt++
// 4. 꺼낸 두 개의 값이 모두 0이면 return -1
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        var Q = new PriorityQueue<Integer>();
        for (int i : scoville) Q.offer(i);
        
        // Q가 비어있지 않고 가장 작은 값이 K를 충족하는지 확인한다.
        while(!Q.isEmpty() && Q.peek() < K) {
            // K는 충족하지 못하나 더 이상 합칠 수 없다.
            if (Q.size() <= 1) return -1;
            // 가장 맵지 않은 음식
            var minValue = Q.poll();
            // 두 번째로 맵지 않은 음식
            var secondMinValue = Q.poll();
            // 0은 아무리 계산해도 충족할 수 없다.
            if (minValue == 0 && secondMinValue == 0) return -1;
            Q.offer(minValue + (secondMinValue * 2));
            answer++;
        }
        
        return answer;
    }
}

 

 

위에서 서술하지는 않았으나 스코빌의 각 원소는 0 이상이라는 표현이 마음에 걸려

굳이 두 수가 모두 0인지의 로직도 추가하였습니다.

 

 

배운 점

스택, 큐는 일상 용어에서도 매우 많이 쓰기 때문에 인지는 하고 있었으나

힙의 개념에 대해서는 까맣게 잊고 있었습니다.

 

예전 취준시절 CS를 공부할 때 기억이 얼핏 남아 있기는 하지만 취업을 위한 공부였기 때문에

쉽게 잊혀진 것 같습니다.

 

사실 이 문제를 풀 때 우선순위 큐의 사용을 떠올려서 망정이지 직접 최소 힙을 구현하려고 했으면

조금 더 많은 시간이 소요됬을 것 같습니다.

 

다만, 경험상 직접 구현한 자료 구조는 그 원리가 머리속에 오래 가기 때문에

기본적인 최소 힙, 최대 힙은 직접 구현해보고 정리를 해두어야 할 것 같습니다.

 

 

오늘의 한줄평

코테 공부 === CS 공부