[P&B] #6 Programmers

프로그래머스 Lv.2 해시, 정렬, 그리디

 

귤 고르기

문제 설명

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

 

나의 문제 풀이 코드 (100/100)

import java.util.*;
class Solution {
    public static int solution(int k, int[] tangerine) {
        int answer = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < tangerine.length; i++) {
            if(map.containsKey(tangerine[i])){
                map.put(tangerine[i], map.get(tangerine[i])+1);
            } else {
                map.put(tangerine[i], 1);
            }
        }

        List<Integer> keySetList = new ArrayList<>(map.keySet());
        Collections.sort(keySetList, (o1, o2) -> (map.get(o2).compareTo(map.get(o1))));

        for(Integer key : keySetList){
            if (k - map.get(key) > 0) {
                k -= map.get(key);
                answer++;
            } else if (k - map.get(key) == 0) {
                answer++;
                break;
            } else {
                answer++;
                break;
            }

        }

        return answer;
    }
}

 

답안 참고 후 수정한 코드

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        HashMap<Integer,Integer> map =new HashMap<>();

        for (int t : tangerine) {
            map.put(t, map.getOrDefault(t, 0) + 1);
        }

        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((o1, o2) -> map.get(o2)-map.get(o1));

        for(Integer key:list){
            k -=map.get(key);
            answer++;
            if(k<=0){
                break;
            }
        }

        return answer;
    }
}

 

문제 풀이 코멘트

문제를 읽어보았을 때 해시맵을 사용하여 value값으로 내림차순 정렬을 하고 value값을 통해 k의 갯수를 줄여가며 key 갯수를 카운트해야겠다는 알고리즘은 바로 머릿속에서 정리가 되었다. 하지만 배열을 해시맵에 넣는 과정에서 getOrDefault함수를 사용하고 싶었는데 사용 방법을 몰라 조건문으로 구현하였다. 그리고 value값을 기준으로 하여 내림차순 정렬하는 방법을 몰라 결국 구글링의 도움을 받았다. 다른 사람들의 코드와 비교하였을 때 구현하고자 하는것은 같았으나 코드의 간결성이 달랐다. 코드를 조금 더 깔끔하게 구현하도록 연습할 필요가 있다.