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

귤 고르기

문제 설명

경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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가지로, 이 값이 최소가 됩니다.

---

해당 문제는 STL map을 활용해 푸는 문제였다.

처음에는, vector<pair<int, int>> 를 활용해 풀었는데, 알고리즘에 오류가 있어 map으로 변경해 풀었다.

 

❌ vector를 활용해 과일을 삭제해나가는 방식으로 풀이

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

using namespace std;

int solution(int k, vector<int> tangerine) {
	int deleteCnt = tangerine.size() - k;
	int typeCnt = *max_element(tangerine.begin(), tangerine.end());

	vector<pair<int, int>> cnt(typeCnt +1);
	for (int t : tangerine)
		cnt[t] = {cnt[t].first + 1, t };

	sort(cnt.begin(), cnt.end());

	for(int i = 1; i < cnt.size(); i++)
	{
		if (deleteCnt == 0) break;

		if (cnt[i].first <= deleteCnt)
		{
			deleteCnt -= cnt[i].first;
			typeCnt--;
		}
	}

	return typeCnt;
}

 

첫번째로 풀이한 방법은 34개의 테스트 케이스 중 단 하나가 계속 틀려서 실패하였다.

 

전체적인 풀이 흐름은 귤의 크기 순으로 개수를 count하여, 개수가 적게 있는 귤을 전체 귤의 개수에서 줄이면서, k개의 귤의 개수가 남을때 남은 지워진 귤의 종류 수를 세는 방식이다.

쉽게말해, 전체 귤에서 개수가 적게있는 귤을 지워나가며 구하는 방식으로 풀었다.

 

문제가 해결되지 않아, 이런 풀이에서 발생한 오류를 예상해보았다.

1. 전체 종류의 수를 map이 아닌 max값을 기반한 vector로 정의하여 오류가 발생할 수 있음
2. 귤의 크기가 1,2,3,4,5 처럼 일렬로 나열되지 않고 1,400,600처럼 나열된다면 오류가 발생할 수 있음

 

이러한 이유로, 풀이 방식을 뒤집어서 생각해보았다.

(문제 해결 후 다른사람의 풀이를 보니 뒤집어서 풀이한거랑 동일한 방식으로 풀이한 것 같다. 나는 왜 처음에 거꾸로 생각했지? ㅎㅎ;)

 

⭕ map을 활용해 과일을 채워나가는 방식으로 풀이

#include <algorithm>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int solution(int k, vector<int> tangerine) {
	map<int, int> type;
	for (int t : tangerine)
		type[t]++;

	vector<int> cnts;
	for (auto t : type)
		cnts.push_back(t.second);

	sort(cnts.begin(), cnts.end(), greater<>());

	int typeCnt = 0;
	for(int i = 0; i < cnts.size(); i++)
	{
		if (k > 0)
		{
			k -= cnts[i];
			typeCnt++;
		}
		else
			break;
	}
	return typeCnt;
}

map을 활용해 귤의 크기 별 개수를 구하고, 

auto로 map의 for문을 돌려 귤의 개수를 담은 vector cnts를 생성해주었다.

 

이후, 개수가 많은 순으로 내림차순 정렬하고 k개의 귤을 다 채울때까지 차례로 귤을 채워주었다.

 

사실 첫번째 풀이와, 두번째 풀이는 거의 동일한 개념인데, 단순 역방향으로 구하는게 성공과 실패에 좌지우지 되었다.

---

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

프로그래머스