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

귤고르기

 

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다.

예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다.

경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 1 ≤ k ≤ tangerine의 길이 ≤ 100,000
• 1 ≤ tangerine의 원소 ≤ 10,000,000

 

입출력 예

k	tangerine	result
6	[1, 3, 2, 5, 4, 5, 2, 3]	3
4	[1, 3, 2, 5, 4, 5, 2, 3]	2
2	[1, 1, 1, 1, 2, 2, 2, 3]	1

 

입출력 예 설명

입출력 예 #1
본문에서 설명한 예시입니다.

입출력 예 #2
경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.

입출력 예 #3
경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.

 

시작 코드

#include <string>
#include <vector>

using namespace std;

int solution(int k, vector<int> tangerine) {
    int answer = 0;
    return answer;
}

 

나의 풀이

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

using namespace std;

int solution(int k, vector<int> tangerine) {
    unordered_map<int, int> count_map;
    
    // 1. 각 크기별 개수 세기
    for (int t : tangerine)
    {
        count_map[t]++; // 키가 t인 요소의 값을 증가시킴
    }

    // 2. 개수만 따로 벡터로 저장 후 정렬
    vector<int> counts;
    
    for (auto& pair : count_map)
    {
        counts.push_back(pair.second); // 카운트 벡터에 카운트 맵에서 가져온 요소의 값을 삽입
    }

    // 3. 내림차순 정렬
    sort(counts.begin(), counts.end(), greater<int>());

    // 4. 많이 가진 종류부터 선택하여 k개 이상 될 때까지 반복
    int answer = 0;
    int total = 0;
    
    for (int c : counts)
    {
        total += c;
        answer++;
        if (total >= k) break;
    }

    return answer;
}

 

코드 분석

1. 해시맵인 unordered_map을 사용하기 위해 count_map으로 생성하고, tangerine을 순회하여 요소를 뽑아 count_map의 키값으로 삽입하고 값을 증가시킵니다.

2. counts 벡터를 만들고 count_map을 순회하여 뽑아낸 요소의 두번째 요소인 값을 counts 벡터에 삽입합니다.

3. counts 벡터를 내림차순으로 정렬합니다.

4. answer와 total 변수를 만들고 counts를 순회하여 요소 c를 뽑아내고 total에 더한다음, answer를 증가시킵니다. 만약 total이 k보다 크거나 같다면 빠져나옵니다.

5. answer 값을 리턴합니다.

 

풀이 설명

이 문제는 키,값을 사용하는 STL 컨테이너 중 해시 컨테이너인 unordered_map을 사용하는 것이 관건입니다. 그냥 키,값을 사용한다면 map을 사용해도 상관없지만, 이 문제에선 정렬이 필요없기 때문에 더 빠른 속도를 자랑하는 unordered_map을 사용하였습니다.

 

경화가 하고싶은 것은 문제 예시에서도 나와있듯이 주어진 귤의 개수와 크기에서 k만큼 담는다고 할 때, 크기가 다른 종류를 최소로 하고 싶은 것입니다. 즉 크기가 겹치는 귤의 개수를 최소로 해야 합니다.

 

첫번째 과정에서 크기별 갯수를 세어 분류를 진행합니다. 두번째에서 우리는 겹치는 크기의 갯수만 필요하기 때문에 갯수를 따로 counts에 담아 저장하고 내림차순으로 정렬합니다. 이제 k개 만큼 담기 위해서 내림차순 정렬된 counts에서 k개를 계산할 임시 변수 total과 담은 크기의 종류를 계산할 answer를 계산하며 최종적으로 if문에서 k개 만큼 담았을 때 완성된 answer 값을 리턴하며 끝이 납니다.

 

<NEXT>

오랜만에 와서 그런지 정답률 순위가 변동이 있긴 했지만, 현재 정답률 기준으로 계속 작성하도록 하겠습니다. 이번에는 정답률 71%의 연습문제 "귤고르기"를 풀어보았습니다. 다음에는 "멀리뛰기" 문제를 살펴보도록 하겠습니다. 감사합니다.