[문제설명]
경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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
[나의 풀이]
import java.util.*;
class Solution {
Map<Integer, Integer> map = new TreeMap<>();
public int solution(int k, int[] tangerine) {
int answer = 0;
for (int e : tangerine) {
map.put(e, map.getOrDefault(e, 0) + 1);
}
// 개수기준으로 정렬
List<Integer> keylist = new ArrayList<>(map.keySet());
Collections.sort(keylist, new customComparator());
// 정렬된 key리스트에서 값을 하나씩 가져와 k에 빼줌
for (Integer e : keylist) {
if (k <= 0)
break;
answer++;
k -= map.get(e);
}
return answer;
}
public class customComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o2).compareTo(map.get(o1));
}
}
}처음에는 "투포인터 문제인가?"라는 생각으로 접근하였었는데, 다시한번 생각해보니 특정한 알고리즘을 통해 푸는 문제가 아닌 구현으로 풀 수 있는 문제였다.
너무 어렵게 생각하지 말구 간단하게 접근해보면, 아래와 같이 정리해볼 수 있다.
내가 고른 귤의 종류가 최소가 되게 하고 싶다 == 개수가 많은 종류부터 고르자
따라서, 먼저 주어진 tangerine배열의 원소를 (종류, 개수)의 쌍으로 HashMap에 저장을 한뒤, 이것의 key값을 Value(개수)기준으로 내림차순 정렬을 해주었다.
그후, key값을 하나씩 가져와서 그에 따른 개수를 k값에서 빼주며 answer를 증가시켰다.
아래는 채점결과이다.
[문제설명]
만약 정렬할때, Comparator부분이 이해가 가질 않는다면, 아래 포스팅을 읽어보시길 추천드립니당.
https://velog.io/@skwx50000/java-Arrays.sort%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90
