[Swift Algorithm] 72411 메뉴 리뉴얼 (2021 카카오 블라인드)

programmers.co.kr/learn/courses/30/lessons/72411

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

 

풀이방법

A~Z의 메뉴중 인기가 많은 조합을 골라내는 문제에요

 

누군가는 ABC를 시킨다면 A, AB, AC, BC, ABC 라는 조합이 가능할거고

누군가는 AC를 시키면 A, AC라는 조합이 가능하겟네요

이때 AB == BA이기 때문에 (라면과 밥, 밥과 라면은 같은 조합이죠)

한번만 체크하기위해서

문자열을 정렬해주고

모든 조합을 검사하면

 

A: 2

AB: 1

AC: 2

BC: 1

ABC: 1

이런 결과가 나오네요

 

이런 논리로 해결해 나가면 쉽게 해결 할 수 있을것 같아요

 

해당 문자열의 모든 조합을 검사

주어진 코스요리의 길이만큼의 조합이 있는지 검사

많이나온 조합의 수를 체크하고 해당 수와 같은 조합이 있는지검사 (많이주문된 메뉴가 여러개라면 모두 배열에 담아야함)

 

// 메뉴 리뉴얼
private func solutionP72411(_ orders:[String], _ course:[Int]) -> [String] {
    var menuSet: [String: Int] = [:]
    var result: [String] = []
    
    // 메뉴마다 나올수있는 코스 조합
    func combination(origin: [Character], n: Int, resultString: String) {
        if resultString.count > 1 && course.contains(resultString.count) {
            if menuSet.keys.contains(resultString) {
                menuSet[resultString]! += 1
            } else {
                menuSet[resultString] = 1
            }
        }
        for i in n+1..<origin.count {
            combination(origin: origin, n: i, resultString: "\(resultString)\(origin[i])")
        }
    }
    
    // 메뉴순회
    for order in orders {
        let menus: [Character] = order.map { $0 }.sorted()
        for i in menus.indices {
            combination(origin: menus, n: i, resultString: "\(menus[i])")
        }
    }
    
    // 가장많은 코스 찾기
    for n in course {
        let max = menuSet.filter { $0.key.count == n && $0.value > 1 }.max { $0.value < $1.value }
        
        if let max = max {
            menuSet.filter { $0.key.count == n }.forEach {
                if $0.value == max.value {
                    result.append($0.key)
                }
            }
        }
    }
    
    print(result.sorted())
    return result.sorted()
}

//solution72411(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2,3,4])
//solution72411(["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2,3,5])
//solution72411(["XYZ", "XWY", "WXA"], [2,3,4])