JArchive 프로그래밍 일기

문제 링크 

리뷰 

항상 가장 작은 수와, 그 다음 작은 수가 필요해서 자동으로 정렬해주는 우선순위 큐를 이용했다. 

우선순위 큐에서 front()를 first로 받고, pop()후에 front()를 second로 받으면 쉽게 접근할 수 있다. 

항상 2개를 꺼내니까 pop()을 2번 해줘야하는 것을 유의하자. 

전부 스코빌지수가 K가 됬는지는 큐의 크기가 1이 됬을 때 검사한다. 

마지막 남은 원소가 K 미만이라면 answer 는 실패다. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> scoville, int K) {
  int answer = 0;
  bool result = true;

  priority_queue<int, vector<int>, greater<int>> pq;

  for(auto s : scoville){ pq.push(s); }

  while(!pq.empty()){

    if(pq.top() > K) break; // 더 검사하지 않아도 된다
    if(pq.size() == 1 && pq.top() < K) { result = false; break; } // 실패

    int first = pq.top();
    pq.pop();
    int second = pq.top();
    pq.pop();

    pq.push(first + (second * 2));
    // cout << "first: " << first << " second:" << second << ' ';
    answer++;
  }
  if(!result) answer = -1;
  return answer;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int k = 7;
  vector<int> scofille = {1, 2, 3, 9, 10, 12};
  cout << solution(scofille, k);

  return 0;
}

문제

더 맵게 프로그래머스 level2

리뷰

힙 카테고리에 있는 문제다.

처음에는 내림차순으로 정렬 후, 뒤에서 첫번째, 두번째 숫자들을 pop_back, 새로 계산한 숫자를 push_back 해서 해결하려고 했었다.

하지만 자꾸 (비용이 큰 함수) sort()를 해야 해서 "실패" 떴다. 그리고 벡터 크기가 2 이상인지도 체크도 안해줬다...

실패한 코드

#include <functional> 

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int last = scoville.size()-1;

    while(scoville[last] >= K){

        sort(scoville.begin(), scoville.end(), greater<int>()); // 내림차순 
        last = scoville.size()-1;
        int new = scoville[last-1]*2 + scoville[last];
        scoville.pop_back();
        scoville.push_back(new);

        answer++;
    }

    return answer;
}

힙 을 사용해서 바꿨다.

priority_queue<int, vector<int>, less<int> > pq; // 오름차순
priority_queue<int, vector<int>, greater<int> > pq; // 내림차순

내림차순으로 정렬한 우선순위 큐를 선언하고, 벡터의 원소를 모두 넣는다.

맨 위에는 가장 작은 값이 오니까 2개 꺼내서 새 값을 계산해서 다시 푸시한다.

이 때, 2개를 꺼내야 하니까, 큐의 사이즈가 1인지 확인하여 예외처리를 해준다.

코드

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int> > pq;
    int answer = 0;

    for(int i=0; i <scoville.size(); i++){ // 벡터 원소를 모두 큐에 넣는다 
        pq.push(scoville[i]);
    }

    while(pq.top() < K){

        if(pq.size() < 2){
            answer = -1; break;    
        } 

        int top = pq.top();
        pq.pop();
        int second = pq.top();
        pq.pop();

        pq.push(second*2 + top);
        answer++;
    }

    return answer;
}