[프로그래머스][JAVA] 귤 고르기

💡 IDEA

우선 문제를 내 방식대로 해석을 했다.

K = 원하는 귤 개수
tangerine = 귤이 담겨있는 배열

tangerine배열에서 K개를 꺼내는데 최대한 적은 종류로 구성해서 꺼내자

이를 가장 먼저 떠오른 방법은 int[] ary = new int[10000001] 이런 식으로 해서 배열 안에 귤의 크기에 맞춰서 ++를 할 생각이었는데..그럴 경우 안에 어떤 크기가 얼마나 들어 있는지가 파악이 불가능해서 이 방법은 아닌 것 같았다.

그래서 생각한 방법은 파이썬에서 dict같이 map을 이용해서 풀려고 했는데 맵은 아래처럼 구성하면 되긴한데..

HashMap<Integer, Integer> map = new HashMap<>();
for(int a : tagerine)
	map.put(a, map.getOrDefault(a,0)+1);

문제는 여기서 정렬을 시키는데 어떻게 값을 기준으로 정렬을 시키는지 몰랐다.
이건 고민한다고 되는 문제가 아니니 서칭을 했는데 많은 사람들이 다른 방식으로 구성을 했고 내가 쉽게 이해할 수 있는 방법으로 풀었다!

키 값을 기준으로 Map정렬하기

1. 값을 꺼내오기 위해 사용할 키 값들을 꺼내온다

List<Integer> KeyList = new ArrayList<>(map.keySet());

2. 키를 이용해 꺼내온 값을 기준으로 정렬을 시작

KeySet.sort((o1,o2) -> map.get(o2).compareTo(map.get(o1)));

이렇게 하면 키 값들을 정렬하는데, 정렬 기준 자체가 키 안에 든 값을 기준으로 하기 때문에 우리가 원하는 값을 얻을 수 있다!

정렬된 키를 이용해서 귤을 가장 많은 거부터 꺼내기

for(int key : KeySet){
	k -= map.get(key);
    answer++;
    if(k <= 0) //k개만큼 다 챙겼다
    	break;
}

💻 전체 코드

import java.util.*;
class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int gul : tangerine)
            map.put(gul, map.getOrDefault(gul,0)+1);
        
        //맵을 꼭 정렬 시킬 필요없이 리스트 형태로 가장 큰 값들만 뽑아오면 된다!
        //키들을 가지는 리스트를 만들고 그 안에서 get(키)해서 결론적으로 값들끼리 비교를 하게 해서 정렬된 키 값을..
        List<Integer> keySet = new ArrayList<>(map.keySet());
        keySet.sort((o1, o2) -> map.get(o2).compareTo(map.get(o1)));

        for(int i : keySet) {
        	k -= map.get(i);//가장 많이 있는 귤부터 담기 시작
        	answer++;//한 종류의 귤을 담았음
        	if(k <= 0)//이미 다 담았으면 종료!
                return answer;
        }
            
        return 1;
    }
}