[C++] 프로그래머스 - 귤 고르기 (Lv.2)

문제 설명

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

프로그래머스

 

문제 해결

생각보다 너무 빨리 풀어서 이게 왜 Lv.2인지 생각하게 된 문제였다.

tangerine 원소가 1000만개 였기 때문에, for loop으로 각 원소에 대해 하나하나 접근해 카운트해도 문제 없어 보였다.

그 후 내림차순 sort를 통해 개수가 가장 많은 귤부터 정렬을 하고,

k값과 answer을 갱신하며 문제를 해결했다.

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(int &a, int &b) {
    return a>b;
}

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    vector<int> count(10000001);
    for(int i=0; i<tangerine.size(); i++) {
        count[tangerine[i]] += 1;
    }
    sort(count.begin(), count.end(), cmp);
    int i=0; 
    while(k>0) {
        k -= count[i];
        i+=1;
        answer += 1;
    }
    return answer;
}

 

결과