초니로그

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

문제 설명

귤 크기를 의미하는 정수 배열이 주어짐

이 중 k개의 귤을 뽑아야 할 때, 크기의 종류 최솟값을 구해야 함

풀이법 구상

<틀린 풀이>

DFS를 활용하여 귤 크기 배열 내 부분 집합을 구하여 최솟값 갱신

-> n은 최대 100,000인데, dfs가 끝날 때마다 ch 배열을 전부 확인하게 되며 O(N^2)의 시간 복잡도를 가지게 됨

import Foundation

var answer = 100000
var ch:[Bool] = []

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    ch = Array(repeating: false, count: tangerine.count)
    dfs(0, tangerine, k)
    return answer
}

func dfs(_ v: Int, _ t:[Int], _ k: Int) {
    if(v == t.count) {
        var sizes = Set<Int>()
        var contain_cnt = 0
        for i in 0..<t.count {
            if(ch[i]) {
                contain_cnt += 1
                sizes.insert(t[i])
            }
        }
        if(!sizes.isEmpty && contain_cnt == k && answer > sizes.count) { 
            answer = sizes.count
        }
        
    } else {
        ch[v] = true
        dfs(v+1, t, k)
        ch[v] = false
        dfs(v+1, t, k)
    }
}

<정답 풀이>

딕셔너리를 통해 귤의 크기 별 개수를 정의

크기 별 개수를 기준으로 딕셔너리를 내림차순 정렬

딕셔너리를 돌며 개수와 종류 수를 누적합하며, 그 값이 k 이상이 될 경우 누적된 종류 수를 반환

(개수가 많은 것부터 탐색하므로 누적된 종류 수는 최소일 수밖에 없음)

코드 구현 (Swift)

import Foundation

func solution(_ k:Int, _ tangerine:[Int]) -> Int {
    var dict:[Int:Int] = [:]
    for t in tangerine {
        if(dict[t] == nil) { dict[t] = 1 }
        else { dict[t]! += 1 }
    }
    let s_dict = dict.sorted { $0.value > $1.value }
    
    var sum = 0
    var answer = 0
    for d in s_dict {
        sum += d.value
        answer += 1
        if(sum >= k) { return answer }
    }
    return answer
}