[TIL] 프로그래머스) 138476 - 귤 고르기 (Java)

 > 휴일 동안 프로그래머스의 '귤 고르기' 문제를 풀고 그 풀이를 적어 보았다.

 

학습 키워드: Java, HashMap, Collections, ArrayList

 

138476 - 귤 고르기

1) 문제 설명 요약 (원문은 하단 링크 참고):

 - 요약. 과수원에서 귤 상자를 포장하는데, k 개의 귤을 포장하는 동안 귤의 크기의 다양성을 최소화했을 때 몇 가지 크기의 귤을 담게 되는지를 찾는 문제입니다. 각각의 귤의 크기는 tangerine 배열(TYPE: int[])에 무작위로 담겨 있습니다.

 - 조건:

   1 <= k <= tangerine.length <= 100,000

   1 <= tangerine[n] <= 10,000,000

 

2-1) 작성한 코드 및 풀이:

import java.util.HashMap;
import java.util.Collections;
import java.util.ArrayList;

class Solution {
    public int solution(int k, int[] tangerine) {
        if (k == 1) return 1;
        HashMap<Integer, Integer> counts = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < tangerine.length; i++) {
            int cur = tangerine[i];
            int count = counts.containsKey(cur) ? counts.get(cur) + 1 : 1;
            counts.put(cur, count);
        }
        
        ArrayList<Integer> list = new ArrayList<Integer>(counts.values());
        Collections.sort(list);
        
        int ret = 0;
        for (int i = list.size() - 1; i >= 0; i--) {
            int cur = list.get(i);
            k -= cur;
            ret++;
            if (k <= 0) break;
        }
        
        return ret;
    }
}

 - 조건만 봤을 때 k가 1인 경우 무슨 수를 써도 한 가지 크기의 귤만 담을 수 있기 때문에, 복잡한 작업이 진행되기 전에 조건문으로 걸러 1을 return하도록 설정해줬다.

 - 문제의 요구 사항대로 최소한의 종류를 사용하려면 우선 귤이 몇 개씩 몇 종류나 있는지를 알아야하는데, 평소처럼 count 배열을 생성하려고 보니 tangerine 값의 크기가 최대 1000만이었다. 10만개의 원소를 체크하는데 길이가 1000만이나 되는 배열을 생성하여 카운팅 하는것은 매우 비효율적(생성할 수는 있나 싶어서 알아보니 21억 5000만개 언저리까지 가능하다고 한다)이어서 결국 HashMap을 이용하기로 했다.

 - 귤 크기마다의 개수를 기억할 HashMap<Integer, Integer> counts 를 생성해준다. Key는 tangerine 배열에 있던 귤의 크기, value는 같은 귤의 크기마다 증가하는 count가 된다.

 - 루프를 돌면서 tangerine 배열의 각 원소를 확인하고, 해당 원소를 key로 하는 데이터가 있는지 확인한 뒤 있으면 가져와서 +1, 없으면 1을 부여하고 put으로 다시 저장해준다.

 - 루프가 끝나면 HashMap 객체의 method인 values()를 사용하여 얻게되는 Collection 객체를 인자로 받는 ArrayList 객체를 생성하고, Collections 클래스의 static 함수인 sort를 이용해 list를 정렬해준다. 이렇게 하면 각각의 개수에 대한 크기는 알 수가 없지만, 요구 사항인 '몇 종류의 귤'을 담는지는 쉽게 알아낼 수 있다.

 - 마지막 루프에서 list를 역순으로 돌면서 귤 요구량인 k에서 귤의 개수 list.get(i)를 빼주면서 귤 종류를 세어주는 변수 ret을 ++해주면 된다. tangerine의 원소가 모두 다른 숫자인게 아닌 이상 루프를 다 돌기 전에 요구량을 맞추게 되므로, 남은 귤의 개수 k가 0 미만이 되면 break로 루프를 이탈할 수 있도록 조건문을 추가해주면 끝난다.

2-2) 성능 요약:

 - 메모리: 97.4 MB, 시간: 45.14 ms

 

3-1) 다른 풀이:

import java.util.HashMap;
import java.lang.Math;

class Solution {
    public int solution(int k, int[] tangerine) {
        if (k == 1) return 1;
        HashMap<Integer, Integer> counts = new HashMap<Integer, Integer>();
        int max = 0;
        
        for (int i = 0; i < tangerine.length; i++) {
            int cur = tangerine[i];
            int count = counts.containsKey(cur) ? counts.get(cur) + 1 : 1;
            if (max < count) max = count;
            counts.put(cur, count);
        }
        
        int[] arr = new int[max + 1];
        for (int i : counts.values()) {
            arr[i]++;
        }
        
        int ret = 0;
        int index = max + 1;
        while (k > 0) {
            int cur = arr[--index];
            if (cur == 0) continue;
            if (index == 1) break;
            int usedKinds = Math.min(Math.max(k / index, 1), cur);
            int usedCount = usedKinds * index;
            k -= usedCount;
            ret += usedKinds;
        }
        
        if (k > 0) ret += k;
        
        return ret;
    }
}

 - 글을 쓰다 보니 귤의 개수가 1개씩인 경우가 10만개에 가까운 경우를 처리하기 위해서 루프를 2까지만 돌고 1을 따로 처리하는 방법이 있었을 것 같아서 코드를 새로 작성해봤는데, 케이스에 따라 속도가 늘기도 해서 평균 처리시간이 딱히 더 줄지 않았다.

 - 그러다가 ArrayList를 사용하기 전에 잠시 고려했었던 counting array를 사용하는 방법으로 다시 작성 해보기로 했다. ArrayList와 Collections를 사용하지 않고 array와 java.lang.Math 클래스를 사용했는데, 아무래도 배열의 길이가 최대 10만이기 때문에 특정 케이스들에서는 여전히 두 자릿수 단위의 ms가 출력되었다. 그래도 평균 시간을 2/3 정도로 줄일 수 있었다.

 

3-2) 성능 요약:

 - 메모리: 94.5 MB, 시간: 30.68 ms

 

4) 기타 사항:

 - 문제를 다 풀고 나서 풀이를 살펴보니 다들 첫 번째 제출했던 코드와 거의 똑같은 방식으로 풀었다. 한 가지 차이점은 HashMap으로 카운팅을 할 때 containsKey를 이용한 삼항 연산을 사용하는 대신 getOrDefault(cur, 0) + 1를 사용하여 기본값을 바로 돌려줄 수 있는 형태로 한 번에 해결하는 풀이가 많이 있었다.