프로그래머스 - 메뉴 리뉴얼 feat. dfs

조합은 for 문으로 구현할 수도 있지만 dfs 로도 경우의 수를 만들어낼 수 있습니다

 

 

 

import Foundation

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    
    var menus: [String:Int] = [:]
    
    for order in orders {
        
        let ordered = order.sorted()
        for courseSize in course {
            let combinations = makeCombination(courseSize, ordered)
            for combination in combinations {
                let combi = String(combination)
                menus[combi, default: 0] += 1
            }
        }
    }
    
    
    var result: [String] = []
    
    for courseSize in course {
        let filtered = menus.filter { $0.value >= 2 && $0.key.count == courseSize }
        let maxCount = filtered.values.max() ?? 0
        let filtered2 = filtered.filter { $0.value == maxCount }
        result.append(contentsOf: filtered2.keys)
    }
    
    
    return result.sorted()
}

func makeCombination(_ n: Int, _ array: [Character]) -> [[Character]] {

    var result: [[Character]] = []
    
    func dfs(_ index: Int, _ combinations: [Character]) {
        if n == combinations.count {
            result.append(combinations)
            return
        }
        
        for i in index..<array.count {
            dfs(i + 1, combinations + [array[i]])
        }
    }
    
    dfs(0, [])
    return result
}