[프로그래머스] 귤 고르기 - 자바

크기가 여러개인 귤 중 k개 만큼의 귤을 골라야 하는데 크기가 서로 다른 종류의 수를 최소로 하고 싶다는 문제

처음에는 무슨 말인가.... 했는데 예시를 보면 이해가 잘 된다.

 

k = 6

tangerine = [1, 3, 2, 5, 4, 5, 2, 3]

 

표로 정리해 보면

크기	개수
1	1
2	2
3	2
4	1
5	2

이 중 6개를 고르려면 개수가 2개인 2, 3, 5 크기를 고르면 될 것이다. 그래서 답이 3인 것

이것은 크기 보다 개수가 중요한 것~!

 

 

그래서 우선은 개수를 알기 위해 크기별 개수를 먼저 구해주었다.

<귤 크기, 개수>로 저장할 HashMap을 만들어 준 후

tangerine 배열에서 가져온 귤 크기를 key로 검색한 value를 +1 해서 저장 (물론 없을 수도 있으니 없으면 0으로 검색)

HashMap<Integer, Integer> tangerineMap = new HashMap<>();
for (int i : tangerine) tangerineMap.put(i, tangerineMap.getOrDefault(i, 0) + 1);

 

이제 개수별로 정렬할 것! 오름차순 보다는 내림차순으로 정렬했다.

이제부터는 크기가 중요하지 않으므로 크기 없이 value 값만 List에 저장해서 sort해도 문제 없음!

// HashMap의 값을 List로 변환
List<Map.Entry<Integer, Integer>> tangerineList = new ArrayList<>(tangerineMap.entrySet());

// HashMap의 Value값을 기준으로 내림차순으로 sort
tangerineList.sort((o1, o2) -> o2.getValue().compareTo(o1.getValue()));

 

정렬된 value 값을 귤 개수(k)에서 뺀 후 answer을 +1 했다.

귤 개수가 다 떨어지면 answer 을 반환

int answer = 0;
for (Map.Entry<Integer, Integer> mapEntry : tangerineList) {
    k -= mapEntry.getValue();
    answer++;
    if (k <= 0) break;
}
return answer;