[012] 귤 고르기

 

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

프로그래머스

 

---

 

진짜 엄청 당황스럽게도... 나는 getOrDefault를 거의 사용해본 적이 없어서 이건 찾아가면서 했다.

(처음에는 hashset을 사용했다가 아 이건 좀... 하면서 뇌가 터져서 검색했음)

 

문제 풀이 자체는 단순하다

1. 제일 많은 것부터 차례로 k에서 뺀다

2. k가 음수가 되는 순간까지 카운트하여 카운트를 리턴한다.

 

다양한 방법이 있지만... (arraylist를 사용할 경우 for문이 3번정도 ^^.. 필요하더라) 계속해서 타임오버가 나서 왜 그런가 했더니 array 형식보다 hashmap이 훨씬 빨라서 (코드도 짧아서 ^^~) 나는 거였음... 하여튼 설명하자면

 

key - value 형식에 해당하는 hashmap을 만들고, 주어진 배열을 순회하면서 map에 담는다.

 

** 중요 : HashMap은 key값의 중복을 허용하지 않는다! 그럼 어떻게 하나? 바로 전의 값을 지우고 현재 넣는 값이 디폴드가 된다! 

key 값은 tangerine 배열의 현재 값이고, getOrDefault 함수를 통해 같은 key를 가지고 있는지를 검증한다. 있다면 그 값 + 1이 value 가 되고, 없다면 default로 지정한 0에 + 1을 한 1이 될 것이다.

 

만약, [ 1, 2, 7, 3, 3, 1, 5 ] 의 배열이 있다고 가정했을 때

map.put(item, map.getOrDefault(item, 0) + 1);

을 사용한다면 순회하며 연산은 아래와 같이 이루어진다

1 -> [1, 1]

2 -> [1, 1] [2, 1]

7 -> [1, 1] [2, 1]  [7, 1]

3 -> [1, 1] [2, 1]  [7, 1] [3, 1]

3 -> [1, 1] [2, 1]  [7, 1] [3, 2]         <- 3이라는 키값이 있으므로 여기에 있던 value값인 1+1

1 -> [2, 1]  [7, 1] [3, 2] [1, 2]          <- 1이라는 키값이 있으므로 원래 존재한 key값을 삭제하고 해당하는 value인 1+1

5 -> [2, 1]  [7, 1] [3, 2] [1, 2] [5, 1]

 

휴... 진짜 처음 쓰는 메소드라 죽어라 이해했음

이후에는 이제 map 타입이었던 것을 연산하기 쉽게(빠르게) 하기 위하여 list로 넣어준다.

연산을 위해 sort를 쓰고, 내림차순 정렬을 해야하므로 람다식을 활용해 내림정렬을 한다. (람다식은 그냥 외우면 된다... )

마지막으로 while문을 이용해 반복을 하는데, 반복이 끝나는 지점은 k에서 계속 수를 뺄 것이기 때문에 k 가 0보다 큰 지점으로 한다. (왜 이 지점으로 하냐면 반복문을 시작하기 전이 아닌 시작한 이후 k에 연산을 하기 때문!) 그리고 반복 횟수를 answer에 넣어준다.

 

반복문이 멈춘 뒤 answer를 리턴하면 끝!

 

    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.List;


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

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

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

        int i = 0;
        while (k > 0){
            k -= map.get(list.get(i));
            answer++;
            i++;
        }

        return answer;
    }
}