[프로그래머스 코딩테스트] 귤 고르기(Java)

  문제 설명

  경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 '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

import java.util.HashMap;
import java.util.Arrays;
class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < tangerine.length; i++) {
            map.put(tangerine[i], map.getOrDefault(tangerine[i], 0) + 1);
        }
        int[] array = new int[map.size()];
        int index = 0;
        for (int i: map.keySet()) {
            array[index++] = map.get(i);
        }
        Arrays.sort(array);
        int sum = 0;
        for (int i = array.length - 1; i >= 0; i--) {
            answer++;
            sum += array[i];
            if (sum >= k) {
                break;
            }
        }
        return answer;
    }
}

  Integer를 제네릭 타입으로 갖는 HashMap을 생성합니다.

  for문이 tangerine의 길이만큼 순회합니다.

  put 메소드로 tangerine의 i 번째 원소를 삽입합니다. value는 getOrDefault 메소드를 이용하여 tangerine의 i 번째 원소가 map에 없다면 key를 추가하고, 있다면 value에 1을 더해줍니다.

  배열 array를 생성하고 크기는 맵의 크기로 지정합니다. 앞선 과정에서 구한 크기별 개수를 배열에 넣어줄 것입니다.

  변수 index를 생성합니다. array의 인덱스를 담당할 것입니다.

  keySet 메소드를 이용하여 for-each문이 맵의 keySet을 순회합니다. 순회한 키 값을 i가 하나씩 받습니다. array의 index 번째 원소에 map의 value를 추가합니다.

  Arrays 클래스의 sort 메소드를 이용하여 array를 오름차순으로 정렬합니다.

  변수 sum을 생성합니다. k와 비교하여 조건을 세울 것입니다.

  for문이 array의 마지막 원소부터 첫 원소까지 역순으로 순회합니다. 최대한 적은 종류로 귤을 담아야 하기 때문에 큰 수부터 더해나가는 것입니다.

  반복문이 진행될 때마다 answer가 증가합니다.

  sum에 array의 i 번째 원소를 더합니다.

  if문에서 sum이 k보다 크거나 같아진다면 break를 이용하여 반복문을 종료합니다.