[99클럽 코테 스터디 25일차 TIL] #힙7

25일 차입니다. 코테 스터디를 한지도 벌써 한 달이 다 되어가네요. 마지막까지 열심히 해보겠습니다. 

 

문제 설명

---

 

음식의 매운 정도가 들어있는 벡터 scoville가 주어지고 원하는 스코빌 지수 k가 차례대로 주어집니다. 모든 음식의 스코빌 지수가 k 이상이 되도록 문제에서 제시한 "섞기"의 방법이 행해지는 최소의 횟수를 구하면 되는 문제입니다.

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

프로그래머스

 

생각 흐름

---

문제 자체는 이해하기 쉬웠던 것 같습니다.

 

숫자 배열이 주어지고 이것들을 "섞기"라는 방법으로 재배열했을 때 정수 k보다 모든 요소가 크면 되었기 때문에 차근차근 코드를 그대로 작성해 보았습니다.

 

오름차순으로 정렬해 주기 위해서 우선순위큐를 priority_queue <int, vector <int>, greater <int>> pq;로 선언해 주었습니다.

또한 섞는 횟수를 저장해 주기 위해 answer이라는 정수형 변수도 선언해 주었습니다.

 

우선, 오름차순 정렬을 위해 scoville 벡터에 있는 요소들을 우선순위 큐 pq에 입력해 주고,

맵기를 본격적으로 비교를 해줘야므로 pq가 비어있지 않고 (pq.size() > 1)  pq의 가장 작은 값 pq.top()이 k보다 작을 경우 계속 돌아가는 while 문을 조건문으로 입력해 주었습니다.

 

문제에서 "섞기"를 하려면 제일 안 매운 음식과 그다음으로 안 매운 음식의 정도를 가지고 연산을 해야므로 이를 first, second을 이용해 정의해 주었고 이를 계산을 통해 다시 재삽입해 주었습니다.

 

문제의 예외사항에서 모든 음식을 k이상으로 만들 수 없는 경우, 즉 pq의 top()이 k보다 작으며 size()가 1인 경우에는 -1이 return 되게 예외처리도 해주며 마무리하였습니다.

#include <iostream>
#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(scoville.begin(), scoville.end()); // scoville의 요소들을 넣은 오름차순 우선순위 큐 pq 선언
    
    while (pq.size() > 1 && pq.top() < K) { // 음식이 1개 이상 있고 pq에서 가장 안 매운 음식이 k지수보다 작을 때
        int first = pq.top(); // 제일 안 매운 음식
        pq.pop();
        int second = pq.top(); // 두번 째로 안매운 음식
        pq.pop();
        pq.push(first + (second * 2));
        answer++;
    }
    if (pq.top() < K)    return -1;
    return answer;
}

 

 

공부한 내용 정리

---

힙을 여러 문제 풀다 보니까 어느 정도 힙에 익숙해진 것 같아서 이번 문제를 풀 때는 딱히 어려운 점을 찾지 못했습니다.

오늘은 여기까지 하고 내일 또 열심히 문제 풀어보겠습니다.