[138476] 귤 고르기

✔ 귤 고르기

[프로그래머스 138476]

문제 분석하기

해시맵에 귤의 종류와 귤의 개수를 저장한 후, 귤의 개수를 리스트에 저장한 후 내림차순 정렬을 하도록 함

이후 서로 다른 종류가 최소이어야 하므로 가장 많은 귤의 개수를 가진 종류부터 담으면서 k개보다 많이 담을 경우를 찾도록 함

 

예) k = 6, [1, 3, 2, 5, 4, 5, 2, 3]

{1:1, 2:2, 3:2, 4:1, 5:2}

list = [2, 2, 2, 1, 1]

2 + 2 + 2 = 3이므로 사용한 귤의 종류는 3개

손으로 풀어보기

1. 해시맵에 귤의 종류와 귤의 개수를 저장
2. 귤의 개수를 리스트에 저장한 후 내림차순 정렬
3. 가장 많은 귤의 개수를 가진 종류부터 담으면서 k개보다 많이 담을 경우를 찾으면 종료
   • 이때 귤의 개수를 가진 종류를 담을 때마다 answer 증가
4. answer 반환

슈도코드 작성하기

k(한 상자에 담으려는 귤의 개수)
tangerine(귤의 크기들)
answer(k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값)
map(귤의 종류와 귤의 개수를 담을 HashMap)
for(t -> tangerine만큼) {
    map.put(t, map.getOrDefault(t, 0) + 1);
}
list(귤의 종류에 따른 귤의 개수를 담을 리스트)
list를 내림차순 정렬
sum(귤의 개수)
for(l -> list만큼) {
    if(sum + l가 k보다 크다면) {
        answer 증가
        break;
    }
    else {
        sum에 l 추가
        answer 증가
    }
}
answer 반환

코드 구현하기

/**
 * 138476) 귤_고르기
 */
public class L085_138476 {
    // k(한 상자에 담으려는 귤의 개수)
    // tangerine(귤의 크기들)
    public int solution(int k, int[] tangerine) {
        // answer(k개를 고를 때 크기가 서로 다른 종류의 수의 최솟값)
        int answer = 0;
        // map(귤의 종류와 귤의 개수를 담을 HashMap)
        Map<Integer, Integer> map = new HashMap<>();
        // map에 귤의 종류에 따른 귤의 개수 담기
        for (int t : tangerine)
            map.put(t, map.getOrDefault(t, 0) + 1);
        // list(귤의 종류에 따른 귤의 개수를 담을 리스트)
        List<Integer> list = new ArrayList<>(map.values());
        // list를 내림차순 정렬
        list.sort(Collections.reverseOrder());
        // sum(귤의 개수)
        int sum = 0;
        for (int l : list) {
            // sum + l가 k보다 크다면
            if (sum + l >= k) {
                // answer 증가
                answer++;
                // k개의 귤을 골랐으므로 종료
                break;
            }
            // sum + l가 k보다 작다면
            else {
                // sum에 l 추가
                sum += l;
                // answer 증가
                answer++;
            }
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L085_138476 solution = new L085_138476();

        int k = 6;
        int[] tangerine = { 1, 3, 2, 5, 4, 5, 2, 3 };

        int result = solution.solution(k, tangerine);

        System.out.println(result);
    }
}