[프로그래머스_Lv.2] 귤 고르기 (Java)

처음 코딩테스트 연습할 때

틀린 문제.

 

항상 어떻게 푸는지 몰라서 방치하다가

오늘 풀어봤는데, 풀려서 은근 놀랐다.

 

---

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/138476

프로그래머스

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 정렬

귤의 크기 차이가 가장 적어야 하므로, 크기마다 귤의 개수를 세주었다.

map을 활용해서 각자의 크기마다 귤이 몇개 있는지 확인하고, 2차원 배열에 저장했다.

그 후 2차원 배열을 정렬하는데, 기준은 귤의 개수가 많은 순이다.

테스트 케이스 1번을 정렬하면 다음과 같다.

 

테스트 케이스 1번을 보면 크기가 5인 귤이 2개, 크기가 4인 귤이 1개, 3인 귤이 2개, 2인 귤이 2개, 1인 귤이 1개 있다.

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

 

귤을 총 6개 골라야한다.

크기가 5인 귤을 2개 고르고, 크기가 4인 귤 2개, 크기가 3인 귤을 2개 고르면 된다. 그러면 총 크기가 3종류로 최소가 된다.

 

풀이 과정

1.

HashMap을 생성 후 크기마다 귤의 개수를 센다.

 

2.

2차원 배열을 생성한 후, 크기와 개수를 저장한다.

 

3.

개수가 많은 순으로 배열을 정렬한다.

 

4.

개수가 많은 귤부터 시작하여 총 필요한 귤의 개수만큼 더한다.

총 필요한 개수가 넘으면 종류를 계산한다. 

 

 

---

코드

import java.util.*;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        
        //크기마다 개수 세기
        Map<Integer, Integer> map = new HashMap();
        for(int i=0; i<tangerine.length; i++){
            map.put(tangerine[i], map.getOrDefault(tangerine[i], 0)+1);
        }
        
        //2차원 배열에 저장 및 정렬
        int[][] arr = new int[map.size()][2];
        int idx = 0;
        for(int key : map.keySet()){
            arr[idx][0] = key;
            arr[idx][1] = map.get(key);
            
            idx++;
        }
        
        Arrays.sort(arr, new Comparator<int[]>(){
           public int compare(int[] o1, int[] o2) {
               return o2[1]-o1[1];
           } 
        });

        //최소 개수 세기
        int sum = 0;
        for(int i=0; i<arr.length; i++){
            sum+=arr[i][1];
            answer++;
            
            if(k<=sum) break;
        }
        
        return answer;
    }
}

 

 

 

(❁´◡`❁)

끝!