[Programmers Level2] 귤 고르기(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가지로, 이 값이 최소가 됩니다.

 

 

[문제 풀이]

 

귤 k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값을 구하는 문제이다.

크기가 서로 다른 종류의 최솟값을 구하기 위해선 종류별로 개수가 큰 순서대로 정렬이 되어야 한다고 생각했다.

 

우선 귤의 종류(크기)에 따른 개수를 셋팅하기 위해 vector 배열을 사용했다.

vector를 귤의 종류(크기)의 개수만큼 크기를 만들고 인덱스를 귤의 크기, 이에 따른 값을 귤의 개수로 생각했다.

 

입출력 예시1로 설명하자면 vector엔 아래와 같이 셋팅된다.

 

그리고 sort 함수를 사용하여 내림 차순으로 정렬한다.

정렬하게 되면 아래와 같이 vector가 변경이 된다.

 

위 상태에서 귤 6개(k)를 고르면 된다.(반복문 사용)

고를 수 있는 귤의 개수 6개에서 크기가 5인 귤 2개를 고르면 4개(k)를 고를 수 있다.

➜ 귤의 종류의 수 +1 증가

 

고를 수 있는 귤의 개수 4개에서 크기가 3인 귤 2개를 고르면 2개(k)를 고를 수 있다.

➜ 귤의 종류의 수 +1 증가

 

고를 수 있는 귤의 개수 2개에서 크기가 2인 귤 2개를 고르면 0개(k)를 고를 수 있다.

➜ 귤의 종류의 수 +1 증가

 

고를 수 있는 귤의 개수(k)가 0보다 같거나 작아진다면 반복문을 끝내면 된다.

최종적으로 귤의 크기가 서로 다른 종류의 수는 3이 된다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

vector<int> box;

void setBox(vector<int>& t) {
    for(int i = 0; i < t.size(); ++i) {
        box[t[i]] += 1;
    }
}

int solution(int k, vector<int> tangerine) {
    sort(tangerine.begin(), tangerine.end(), greater<int>());
    box.resize(tangerine[0] + 1);
    setBox(tangerine);
    sort(box.begin(), box.end(), greater<int>());
    int answer = 0;
    for(int element : box) {
        if(k <= 0) break;
        answer +=1;
        k -= element;
    }
    return answer;
}