42626. 더 맵게

Approach

처음엔 벡터를 사용해서 리버스 정렬 한 다음 뒤에서 부터 스코빌 값을 확인했다. 값이 K보다 작으면 뒤에 2개의 값을 가지고 계산, 그리고 반복.

(지금 쓰면서 느낀건데 왜 리버스 정렬을 했지..? 작성할 때는 sort가 내림정렬이라고 착각했나보다)

Attempt

1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(vector<int> scoville, int K) {
5    int answer = 0;
6    sort(scoville.rbegin(), scoville.rend());
7    
8    for(int x : scoville) cout << x << ' ';
9    cout << endl;
10    
11    while(!scoville.empty() && scoville[scoville.size() - 1] < K) {
12        if(scoville.size() == 1) return -1;
13        
14        int last = scoville.back();
15        scoville.pop_back();
16        scoville[scoville.size()-1] = last + scoville[scoville.size()-1]*2;
17        ++answer;
18    }
19    return answer;
20}

Issues

로직이 틀렸다. 두 개의 수를 더해서 다시 집어넣으면 정렬이 흐트러질수가 있는데 이를 깜빡했다. 재정렬을 해주어야 한다.

하지만 heap문제이기도 하니, 연결리스트가 아닌 priority queue를 사용하기로 했다.

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4int solution(vector<int> scoville, int K) {
5    int answer = 0;
6    priority_queue<int, vector<int>, greater<int>> q;
7    for(int x : scoville) q.push(x);
8        
9    while(true) {
10        if(q.size() == 1 && q.top() < K) return -1;
11        if(q.top() >= K) break;
12        
13        if(q.top() < K) {
14            int first = q.top();
15            q.pop();
16            int second = q.top();
17            q.pop();
18            
19            q.push(first + second*2);
20        }
21        ++answer;
22    }
23    return answer;
24}

Time Complexity

O(N * log N)

Space Complexity

O(N)