M'S Blog

M'S Blog

WWDC20 student challenge Winner!

프로그래머스 - 더 맵게

최대 1 분 소요

문제

프로그래머스 - 더 맵게 풀러가기

문제 분석

모든 음식의 스코빌 지수가 k이상이 되도록 만들어야 한다.

그렇다면 모든 음식의 스코빌 지수 중 최소값이 k 이상이 되도록 만들면 된다.

즉, 정렬을 이용하면 된다.

힙은 데이터를 삽입하고, 제거하는데 각각 logn의 시간 복잡도를 가진다.

최소 힙은 부모 노드의 값이 자식 노드의 값 보다 작다. 따라서, 루트 노드의 값이 최솟값을 가진다.

c++의 경우 priority queue를 이용하면 힙을 쉽게 구현 할 수 있다.

이를 이용하여 문제를 풀어본다.

문제 코드(C++)

  1. 전체 코드

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    #include <string>
    #include <vector>
    #include <queue>
     
    using namespace std;
     
    int solution(vector<int> scoville, int K) {
        int answer = 0;
     
        priority_queue<int, vector<int>, greater<int>> pq;
        
        for(int i = 0;i<scoville.size();i++){
            pq.push(scoville[i]);
        }
        
        while(!pq.empty()){
            if(pq.top()>=K){
                break;
            }
            if(pq.size() == 1){
                if(pq.top()<K){
                    answer = -1;
                    break;
                }
            }
            int n1 = pq.top();
            pq.pop();
            int n2 = pq.top();
            pq.pop();
        
            int n = n1+n2*2;
            pq.push(n);
            answer++;
        }
        
        return answer;
    }
    		cs
    • 10번째 줄 : priority queue를 오름차순으로 만든다. 이렇게 하면 min heap을 만들 수 있다.
    • 16~34번째 줄 : priority queue가 빌 때까지 반복문을 진행한다.
      • 17~19번째 줄 : priority queue의 top, 즉 루트 노드의 값이 k와 같거나 크다면 모든 음식의 스코빌 지수는 k이상이라고 할 수 있다. 따라서 반복문을 중단한다.
      • 20~25번째 줄 : 작은 두 값끼리 연산을 반복 한 뒤 priority queue에 하나만 남았는데, 그 하나가 k보다 작다면 모든 음식의 스코빌 지수를 k이상으로 만들 수 없는 경우다. 따라서 answer를 -1로 만들고 반복문을 중단한다.
      • 26~33번째 줄 : 제일 작은 두 값을 꺼내서 새로운 스코빌 지수를 생성한 뒤 그 값을 priority queue에 넣어주고 횟수(answer)를 증가시킨다.





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고