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

 

 

🍄 코딩테스트 문제 풀이

✍🏻 문제 풀이 github 링크

 

 

문제 설명

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

• 본문에서 설명한 예시입니다.

 

입출력 예 #2

• 경화는 크기가 2인 귤 2개와 3인 귤 2개 또는 2인 귤 2개와 5인 귤 2개 또는 3인 귤 2개와 5인 귤 2개로 귤을 판매할 수 있습니다. 이때의 크기 종류는 2가지로 이 값이 최소가 됩니다.

 

입출력 예 #3

• 경화는 크기가 1인 귤 2개를 판매하거나 2인 귤 2개를 판매할 수 있습니다. 이때의 크기 종류는 1가지로, 이 값이 최소가 됩니다.

 

 

 

 

문제 풀이

나의 풀이

import Foundation

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    
    var dic = [Int:Int]()
    var k = k, count = 0
    
    for i in tangerine {
        dic[i] = ( dic[i] ?? 0 ) + 1
    }
    
    for i in dic.values.sorted(by: >){
        k -= i
        count += 1
        if k <= 0 {
            return count
        }
    }
    
    return 0
}

tangerine 길이의 최댓값이 100,000 이었기 때문에 반복문을 한 번만 돌아서 풀 수 있도록 해야했다. 결국 한 번은 각 숫자들의 개수를 찾아서 내림차순으로 정리를 해야하는데, 이때, 비교가 시간이 가장 짧을 딕셔너리로 택했다. 한번의 for문을 돌며 딕셔너리에 해당 크기들의 개수를 얻고, 해당 크기들의 개수를 내림차순으로 하여 그 값들을 k에서 하나씩 빼서 k가 0보다 작거나 같을 경우에 for문을 빠져나옴과 동시에 답을 출력하도록 하였다.

 

 

다른 사람 풀이

func solution(_ k: Int, _ tangerine: [Int]) -> Int {
    return Dictionary(grouping: tangerine) { $0 }.values
        .sorted { $0.count > $1.count }
        .reduce((0, 0)) { acc, array in acc.1 >= k ? acc : (acc.0 + 1, acc.1 + array.count) }
        .0
}

 

 

나도 처음엔 reduce로 풀려고 했는데, 중간에 if문을 빠져나올 수 없어서 쓰지 못했다.

하지만, 클로저 안에 return을 주는 것이 아닌 return 값 뒤에 reduce라는 문장을 한번에 써서 딕셔너리를 내림차순으로 정렬하여 하나씩 값을 더할 때 이 값이 k보다 크다면 아무것도 더하지 않고, k보다 작다면 갯수를 하나 올리고, 값을 계속 더하는 것이다.

 

그렇다면 궁금한 건 acc.1이 k보다 크거나 같을 경우엔 뒤의 acc 더이상의 반복문을 돌지 않고 그대로 빠져나오는 것인가 아님 반복문을 계속 돌지만, 계산을 안하는 것인가? 

reduce는 중간에 배열 값을 빠져나오지 않기 때문에 100,000개의 배열에서 2번째 원소에서 해당 조건을 만족했다고 하더라도 아무 연산이 일어나지 않지만 나머지 99,998개의 배열을 다 돈다고 하였다. 그럼 더 비효율적인게 아닌가!!!!

 

 

중요한 개념

Dictionary(grouping: 그룹화할 배열, by: 그룹화할 기준)

let students = ["Kofi", "Abena", "Efua", "Kweku", "Akosua"]
let studentsByLetter = Dictionary(grouping: students, by: { $0.first! })
// ["E": ["Efua"], "K": ["Kofi", "Kweku"], "A": ["Abena", "Akosua"]]

 

Dictionary에서 해당 값을 그룹화하면 그룹화된 값들이 배열로 딕셔너리에 저장이 된다!

앞으로 자주 쓸 듯!ㅎ