스택/큐

주식가격

#include <string>
#include <vector>
#include <stack>

using namespace std;

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<pair<int, int>> bucket;
    
    for (int i=0; i<prices.size(); i++) {
        while (!bucket.empty() && bucket.top().second > prices[i]) {
            answer[bucket.top().first] = i - bucket.top().first;
            bucket.pop();
        }
        
        bucket.push({i, prices[i]});
    }
    
    while (!bucket.empty()) {
        answer[bucket.top().first] = prices.size() - bucket.top().first - 1;
        bucket.pop();
    }
    
    return answer;
}

/*
정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.97MB)
  테스트 2 〉	통과 (0.03ms, 3.95MB)
  테스트 3 〉	통과 (0.17ms, 3.96MB)
  테스트 4 〉	통과 (0.20ms, 3.83MB)
  테스트 5 〉	통과 (0.21ms, 3.94MB)
  테스트 6 〉	통과 (0.02ms, 3.96MB)
  테스트 7 〉	통과 (0.12ms, 3.96MB)
  테스트 8 〉	통과 (0.14ms, 3.91MB)
  테스트 9 〉	통과 (0.02ms, 3.93MB)
  테스트 10 〉	통과 (0.23ms, 3.98MB)

효율성  테스트
  테스트 1 〉	통과 (25.96ms, 24.2MB)
  테스트 2 〉	통과 (19.16ms, 18.8MB)
  테스트 3 〉	통과 (28.64ms, 26.8MB)
  테스트 4 〉	통과 (22.42ms, 21.3MB)
  테스트 5 〉	통과 (14.86ms, 16.2MB)
  
채점 결과
  정확성: 66.7
  효율성: 33.3
  합계: 100.0 / 100.0
*/

힙(Heap)

더 맵게

#include <string>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int times = 0;
    
    priority_queue <int, vector<int>, greater<>> foods;
    
    for (int f : scoville) foods.push(f);
    
    while (foods.top() < K) {
        int least_spicy_food = foods.top();
        foods.pop();
        
        if ((foods.size() < 1) || (least_spicy_food + foods.top() == 0)) return -1;
        
        foods.push(least_spicy_food + 2 * foods.top());
        foods.pop();
        
        times++;
    }
    
    return times;
}

/*
정확성  테스트
  테스트 1 〉	통과 (0.01ms, 3.98MB)
  테스트 2 〉	통과 (0.01ms, 3.95MB)
  테스트 3 〉	통과 (0.01ms, 3.93MB)
  테스트 4 〉	통과 (0.01ms, 3.94MB)
  테스트 5 〉	통과 (0.01ms, 3.96MB)
  테스트 6 〉	통과 (0.09ms, 3.96MB)
  테스트 7 〉	통과 (0.07ms, 3.84MB)
  테스트 8 〉	통과 (0.01ms, 3.96MB)
  테스트 9 〉	통과 (0.01ms, 3.97MB)
  테스트 10 〉	통과 (0.06ms, 3.96MB)
  테스트 11 〉	통과 (0.04ms, 3.95MB)
  테스트 12 〉	통과 (0.13ms, 3.95MB)
  테스트 13 〉	통과 (0.07ms, 3.93MB)
  테스트 14 〉	통과 (0.01ms, 3.77MB)
  테스트 15 〉	통과 (0.10ms, 3.96MB)
  테스트 16 〉	통과 (0.01ms, 3.98MB)

효율성  테스트
  테스트 1 〉	통과 (28.11ms, 9.32MB)
  테스트 2 〉	통과 (55.10ms, 14.9MB)
  테스트 3 〉	통과 (226.55ms, 39.8MB)
  테스트 4 〉	통과 (19.95ms, 7.87MB)
  테스트 5 〉	통과 (235.44ms, 41.3MB)

채점 결과
  정확성: 76.2
  효율성: 23.8
  합계: 100.0 / 100.0
*/