C++ / 프로그래머스 / 귤 고르기

문제

 

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

프로그래머스

문제풀이

 

우선순위 큐를 이용하여 풀었다.

정렬을 한 뒤, 이번 귤과 다음귤이 같지 않으면 cnt값을 우선순위 큐에 push 한다.

그렇게 되면 우선순위 큐에는 크기가 같은 귤들이 몇 개씩 있는지, 개수만 들어간다.

따로 정렬 설정을 안 했으므로 우선순위 큐 top부분에는 가장 큰 숫자가 들어간다.

 

반복문을 돌려 K가 0 이하가 될 때까지 K - pq.top()을 하여 상자에 귤을 담는다.

귤을 담았으므로 담은 횟수를 증가시킨다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer(0), idx(0), cnt(0);
    priority_queue<int>pq;

    sort(tangerine.begin(), tangerine.end());
    tangerine.push_back(-1);

    for (idx = 0; idx < tangerine.size(); ++idx) {
        ++cnt;
        if (tangerine[idx] != tangerine[idx + 1]) {
            pq.push(cnt);
            cnt = 0;
        }
    }

    while (k > 0) {
        k -= pq.top();
        pq.pop();
        answer++;
    }

    return answer;
}