코딩테스트 연습 - 메뉴 리뉴얼

문제 풀이 아이디어

주어진 주문을 가지고 세트 메뉴를 만들어야 하는데요. 세트 메뉴를 만들 때는 순서는 관계 없으니까 조합을 사용해서 세트 메뉴를 구현하면 됩니다. 각각의 주어진 order를 가지고 세트 메뉴가 될 수 있는 세트 후보들을 구하고 그 후보들을 주어진 조건에 맞는 것만 필터링해서 정답을 구하면 됩니다.

조합을 가지고 푸는 아이디어만 얻는다면 그렇게 어렵지는 않지만 문제가 길어서 조합으로 나온 후보들 중에 어떤 것만을 선택해야 하는지 파악하는 능력이 더 중요하다고 생각합니다.

코드

// 전체 메뉴를 구하지 않고 부분의 메뉴만을 구한 방법
func solution(_ orders:[String], _ course:[Int]) -> [String] {
    
    // 주문으로 만들 수 있는 세트의 조합
    var candidates = [String:Int]()

    // 주문을 받아서 세트를 만드는 함수
        //👉 dfs릃 활용해서 조합(combination)을 방법과 동일한 원리
    func findCandidates(_ index: Int, order: [String], now: String) {
        
        // 세트가 course의 최대 길이보다 커지면 리턴 (탈출 조건)
        if now.count > course.last! {
            return
        }
        
        for i in index..<order.count {
            let new = now + order[i]
            // 세트의 길이가 course 안에 있다면
            if course.contains(new.count) {
                candidates[new, default: 0] += 1 //👉 candidates에 += 1
            }
            findCandidates(i + 1, order: order, now: new)
        }
        
    }

    // 주문들을 가지고 세트의 조합을 모두 구하기
    for order in orders {
        findCandidates(0, order: order.map { String($0) }.sorted(), now: "")
        //❗️주문이 알파벳 순서대로 주어지는 것이 아니므로 정렬해야 함!
    }
    
    // 세트의 길이별 최대 값을 저장하는 배열 (세트의 최대 길이 10)
    var max = Array(repeating: 0, count: 11)
    
    // 모든 세트를 순회하면서 세트의 길이별로 최댓값을 구한다
        //👉 최댓값을 가진 세트가 2개 이상인 경우에 모두 출력해야 하므로
    for candidate in candidates.keys {
        if max[candidate.count] < candidates[candidate]! {
            max[candidate.count] = candidates[candidate]!
        }
    }

    return candidates.keys.filter { max[$0.count] > 1 && candidates[$0] == max[$0.count] }.sorted()
        //👉 세트 후보 중에서 1번만 선택된 세트는 제외하고
        //👉 세트 후보 중에서 가장 많이 선택된 세트만 filter
        //👉 그리고 정렬해서 정답으로 리턴
}