코딩테스트 연습 - 귤 고르기

문제 풀이 아이디어

겉보기에는 어떻게 보일지 모르지만 문제를 차분하게 읽어보면 그렇게 어려운 문제가 아닙니다. 가장 적은 귤의 “종류”로 한 상자를 채우면 됩니다. 이렇게 하기 위한 가장 간단한 방법은 바로 귤의 크기의 종류별로 몇개씩 있는지 구하고 가장 많은 귤의 크기부터 상자를 채워나가면 됩니다. 그리디 알고리즘을 사용하는 방법입니다.

코드

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    // 귤을 크기-갯수의 dict로 만들기
    var dict = [Int:Int]()
    for t in tangerine {
        dict[t, default: 0] += 1
    }
    
    // 귤의 크기를 갯수가 많은 순서대로 정렬
    let keys = dict.keys.sorted { dict[$0]! > dict[$1]! }
    
    // 귤의 크기의 "종류 수"
    var cnt = 0
    // 상자에 들어갈 귤의 총합
    var sum = 0
    
    // 가장 갯수가 많은 큘의 크기부터 상자에 넣고
    for key in keys {
        sum += dict[key]!
        cnt += 1
        // 상자에 들아간 귤이 k 이상일 때 break
        if sum >= k { break }
    }
    
    return cnt
}