<프로그래머스 C++> 귤 고르기 풀이 (unordered_map, greedy)

문제

귤 k개를 골라 상자에 담을 때 크기 종류의 수를 최소화하는 문제이다.

귤의 크기별 개수를 세고, 개수가 많은 순서대로 담아 종류를 최소화할 수 있다.

---

풀이 아이디어

종류 수를 최소화하려면 개수가 많은 크기부터 먼저 담으면 된다.

 

[1, 3, 2, 5, 4, 5, 2, 3]에서 크기별로 개수를 세면 다음과 같다.

2 → 2개
3 → 2개
5 → 2개
1 → 1개
4 → 1개

 

개수 많은 순으로 정렬하면 [2, 2, 2, 1, 1,]

 

k = 6이면 2 + 2 + 2 = 6으로 세 종류를 담을 수 있다.

 

문제 해결 흐름

1. unordered_map으로 크기별 개수를 센다.
2. 개수만 꺼내 내림차순으로 정렬한다.
3. 개수가 많은 순서대로 k에서 빼며 종류 수를 센다.
4. k가 0이하가 되는 순간 종료한다.

---

문제 풀이

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

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    unordered_map<int, int> ans;

    for(int fruit : tangerine)
        ans[fruit]++;

    vector<int> count;
    for(auto const& pair : ans)
        count.push_back(pair.second);

    sort(count.begin(), count.end(), greater<int>());

    for(int cnt : count)
    {
        k -= cnt;
        answer++;
        if(k <= 0) break;
    }
    return answer;
}

---

unordered_map VS map

개수를 세는 자료구조로 map과 unordered_map을 고민한 끝에 unordered_map을 사용했다.

 

두 자료구조의 차이는 다음과 같다.

	map	unordered_map
내부 구조	레드 - 블랙 트리	해시 테이블
삽입 / 탐색	O(log N)	O(1) 평균
키 정렬	자동 정렬	정렬 없음

 

이 문제에선 귤 크기(key) 기준 정렬이 필요 없고 단순히 개수만 세면 된다.

map을 써도 정답 처리는 되겠지만 키를 자동 정렬하는 과정이 들어가 O(N log N)이 소요된다.

 

unordered_map을 사용하면 개수를 세는 과정을 O(N)으로 최적화할 수 있어 훨씬 빠르다.

---

코드 흐름

1. 크기별 개수 세기

unordered_map<int, int> ans;
for(int fruit : tangerine)
    ans[fruit]++;

 

귤 크기를 키, 개수를 값으로 저장한다.

unordered_map을 이용해서 O(N)으로 처리할 수 있다.

 

2. 개수만 추출해서 내림차순 정렬

vector<int> count;
for(auto const& pair : ans)
    count.push_back(pair.second);

sort(count.begin(), count.end(), greater<int>());

크기는 상관없이 종류만 계산하면 되므로 pair.second만 꺼내 사용한다.

 

greater<int>()를 이용하면 내림차순 정렬이 가능하다.

 

3. 그리디 방식으로 담기

for(int cnt : count)
{
    k -= cnt;
    answer++;
    if(k <= 0) break;
}

개수가 많은 순서대로 k에서 빼면서 종류 수를 센다.

 

k가 0이하가 되는 순간 k개를 다 채운 것이므로 종료한다.

---

핵심 포인트

 

• 종류 수를 최소화하려면 개수가 많은 크기부터 담는 그리디 전략을 사용한다.
• 단순 개수 세기에는 map보다 unordered_map이 O(N)으로 더 효율적이다.
• 크기(키)는 필요 없으므로 개수(값)만 꺼내 정렬한다.