04/02 알고리즘 공부(83) - 귤 고르기

조건

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

입출력 예

k	tangerine	result
6	[1,3,2,5,4,5,2,3]	3
4	[1,3,2,5,4,5,2,3]	2
2	[1,1,1,1,2,2,2,3]	1

알고리즘 예상

1. 우선 단순하게 count를 이용하는 방법부터 생각해보자.
   i in 1..tangerine.maxOf{it}에서 tangerine.count(i)를 하면 크기별로 몇 개의 귤이 있는지 확인할 수 있다. k가 될 때까지 많은 크기의 수 부터 더하면 된다.
   이 방법의 경우 tangerine의 길이와 원소의 크기가 굉장히 크기 때문에 시간초과가 뜰 것이라고 예상된다.
2. groupBy를 이용해서 크기에 맞춰서 그룹화 한 다음 갯수에 맞춰 정렬하는 방법도 생각해보자.
   groupBy{ it }을 이용하면 같은 값끼리 모아서 Pair<key = 값, value = 해당 값의 개수만큼 해당 값을 원소로 가지는 리스트> 형태로 반환해준다.
   따라서 map을 이용해 (key to value의 길이)로 바꾸면 tangerine에 count를 사용하지 않고 개수를 셀 수 있다.

 

초기 코드

class Solution {
    fun solution(k: Int, tangerine: IntArray): Int {
        var answer: Int = 0
        return answer
    }
}

 

내 코드

// 통과
class Solution {
    fun solution(k: Int, tangerine: IntArray): Int {
        var answer: Int = 0
        val tangerineGroup = tangerine
            .groupBy { it }
            .map { it.key to it.value.count() }
            .sortedBy { it.second }
            .reversed()
            
        var count = 0
        while (count < k) {
            count += tangerineGroup[answer].second
            answer++
        } 
        
        return answer
    }
}

 

 

다른 사람의 풀이

class Solution {
    fun solution(k: Int, tangerine: IntArray): Int {
        var answer: Int = 0
        var limit = 0
        tangerine.groupBy { it }.toList().sortedByDescending { it.second.size }.forEach{
        if(limit >= k){
            return answer
        }
        limit += it.second.size
        answer++
    }

    return answer
    }
}

 

개선점 또는 배운점

//count()를 사용했을 때

테스트 1 〉	통과 (34.21ms, 72.3MB)
테스트 2 〉	통과 (34.44ms, 73.7MB)
테스트 3 〉	통과 (34.99ms, 73.3MB)
테스트 4 〉	통과 (32.08ms, 72.2MB)
테스트 5 〉	통과 (43.39ms, 69.1MB)
테스트 6 〉	통과 (42.35ms, 69.5MB)
테스트 7 〉	통과 (49.49ms, 70.8MB)
테스트 8 〉	통과 (43.21ms, 70.5MB)
테스트 9 〉	통과 (39.71ms, 72MB)
테스트 10 〉	통과 (35.56ms, 71.6MB)
테스트 11 〉	통과 (17.52ms, 63.5MB)
테스트 12 〉	통과 (8.66ms, 60MB)
테스트 13 〉	통과 (20.56ms, 64.3MB)
테스트 14 〉	통과 (7.63ms, 60.4MB)
테스트 15 〉	통과 (19.29ms, 64MB)
테스트 16 〉	통과 (10.90ms, 60MB)
테스트 17 〉	통과 (17.16ms, 63.2MB)
테스트 18 〉	통과 (18.91ms, 63.7MB)
테스트 19 〉	통과 (6.77ms, 63MB)
테스트 20 〉	통과 (17.14ms, 63.9MB)
테스트 21 〉	통과 (18.26ms, 64MB)
테스트 22 〉	통과 (20.30ms, 63.9MB)
테스트 23 〉	통과 (29.25ms, 63.7MB)
테스트 24 〉	통과 (19.10ms, 64.2MB)
테스트 25 〉	통과 (36.37ms, 68MB)
테스트 26 〉	통과 (38.94ms, 69.3MB)
테스트 27 〉	통과 (85.37ms, 99.6MB)
테스트 28 〉	통과 (56.64ms, 82.7MB)
테스트 29 〉	통과 (85.49ms, 95.6MB)
테스트 30 〉	통과 (97.24ms, 98.4MB)
테스트 31 〉	통과 (33.90ms, 70.7MB)
테스트 32 〉	통과 (37.17ms, 72.8MB)
테스트 33 〉	통과 (90.42ms, 98.1MB)
테스트 34 〉	통과 (96.69ms, 96.2MB)

// size를 사용했을 때

테스트 1 〉	통과 (36.37ms, 73.9MB)
테스트 2 〉	통과 (39.12ms, 72.2MB)
테스트 3 〉	통과 (34.77ms, 73.3MB)
테스트 4 〉	통과 (34.24ms, 72.2MB)
테스트 5 〉	통과 (35.56ms, 68.8MB)
테스트 6 〉	통과 (32.48ms, 69.5MB)
테스트 7 〉	통과 (34.40ms, 70.9MB)
테스트 8 〉	통과 (31.04ms, 71.6MB)
테스트 9 〉	통과 (33.98ms, 69.5MB)
테스트 10 〉	통과 (34.36ms, 72.1MB)
테스트 11 〉	통과 (18.84ms, 63.4MB)
테스트 12 〉	통과 (6.86ms, 61.7MB)
테스트 13 〉	통과 (17.98ms, 63.6MB)
테스트 14 〉	통과 (7.11ms, 60.9MB)
테스트 15 〉	통과 (21.18ms, 63.2MB)
테스트 16 〉	통과 (6.96ms, 63.1MB)
테스트 17 〉	통과 (25.79ms, 63.3MB)
테스트 18 〉	통과 (24.02ms, 64.3MB)
테스트 19 〉	통과 (7.46ms, 62.3MB)
테스트 20 〉	통과 (22.24ms, 62.7MB)
테스트 21 〉	통과 (19.21ms, 64.2MB)
테스트 22 〉	통과 (19.18ms, 63.6MB)
테스트 23 〉	통과 (20.39ms, 64.5MB)
테스트 24 〉	통과 (19.77ms, 63.4MB)
테스트 25 〉	통과 (41.06ms, 69.5MB)
테스트 26 〉	통과 (66.06ms, 71.4MB)
테스트 27 〉	통과 (154.57ms, 98.9MB)
테스트 28 〉	통과 (85.23ms, 83.5MB)
테스트 29 〉	통과 (104.48ms, 96.2MB)
테스트 30 〉	통과 (96.65ms, 98.4MB)
테스트 31 〉	통과 (31.77ms, 71.1MB)
테스트 32 〉	통과 (36.45ms, 72.7MB)
테스트 33 〉	통과 (95.84ms, 97.7MB)
테스트 34 〉	통과 (83.39ms, 95.8MB)

1. count와 size를 각각 이용해 봤을 때 몇몇 케이스에서는 count가 빠르고 어떤 케이스는 비슷하고 어떤 케이스에서는 느렸다. 그룹화 했을 때 나온 value의 길이에 따라 성능차이가 나는 것으로 예상된다.
2. 나는 while문을 이용해 k값을 맞춰갔지만 풀이에서는 forEach문과 조건문을 이용해 return했다.

 

개선된 코드

class Solution {
    fun solution(k: Int, tangerine: IntArray): Int {
        var answer: Int = 0
        var count = 0
        tangerine.groupBy { it }
            .map { it.key to it.value.count() }
            .sortedBy { it.second }
            .reversed()
            .forEach{
                count += it.second
                answer ++
                if(count >= k) return answer
            }
        return answer
    }
}