PS

swift 카카오 코딩테스트 메뉴 리뉴얼

dever 2021. 6. 24. 13:12

문제설명

문제를 정말 잘 이해 해야한다. 아무리 강조해도 지나치지 않는데.. 이 문제는 사실 이해하기 조금 힘든? 문제지 않았나 싶다. 문제가 설명이 조금.. 부족했달까..
정리하자면 손님별로 레스토랑에서 음식을 주문하는데 음식은 A-Z 알파벳으로 표현된다. 손님1은 A, B, C 손님2는 A, B, D 이렇게 단품의 조합으로 음식을 주문한다. 여기서 문제가 요구하는 것은 이 단품들을 코스요리로 만드는것이 문제다. 가장 손님들이 많이 시켜먹은 조합으로 해야하는데 다시 예를 들면 손님1 = ABC, 손님2 = ABD, 손님3 = ABE 이렇게 주문했다고 하면 두개의 단품메뉴로 만들 수 있는 코스요리는 AB, AC, AD, AE, BE... 등등 많을 수 있지만 이 중에서 가장 많이 등장한 코스로 결정한다는 것이다. 위와 같은 예시에서는 AB가 횟수 3번으로 가장 많이 등장하게 된 것이다. 몇개의 메뉴로 코스로 결정할지는 course 파라미터를 통해 제공 된다. 많이 등장한 코스메뉴가 같다면 둘다 출력 해주면 된다. 문제 설명은 간단히 마치고 코드를 살펴보겠다.

코드

func combination(_ str: String, len: Int) -> [String] {
    if str.count < len {
        return []
    }

    if len == 1 {
        return str.map { String($0) }
    }

    guard let first = str.first else { return []}
    let newString = String(str.dropFirst())
    let c = String(first)

    return combination(newString, len: len)
        + combination(newString, len: len - 1).map { c + $0 }
}

func solution(_ orders:[String], _ course:[Int]) -> [String] {

    let ret = course.map { num -> [String] in
        let counts = orders
            .map { combination($0, len: num) }
            .flatMap { $0 }
            .map { $0.sorted().map{ String($0) }.joined() }
            .reduce(into: [:], { counts, word in
                counts[word, default: 0] += 1
            })
        guard let max = counts.values.max(), max >= 2
        else { return [] }
        let keys = counts.filter { $0.value == max }
            .map { $0.key }
        return keys
    }

    return ret.joined().sorted()
}

코드 설명

Combination

먼저 Combination이 필요하다. 예를 들어 손님1이 ABCDEFG의 7개의 단품을 주문했다고 한다면 이 단품메뉴를 가지고 3가지로 구성된 코스메뉴를 개발한다고 한다면 7C3의 경우의 수가 나올 것이다. 이것을 다 구하기 위해 문자열이 주어진다면, 재귀함수로 가능한 모든 경우를 반환하는 함수를 작성했다. 먼저 조합이란 것은 nCr = n-1Cr + n-1Cr-1 의 합이다. 이것이 의미하는 것은 10개중 3개를 뽑는 방법은 하나를 뽑고 나서 그것을 뺀 9개에서 2개를 뽑는 방법과 하나를 제외하고 (뽑지 않고) 9개중 3개를 뽑는 방법의 합으로 나타낼 수 있다. 그것을 코드로 구현한 것인데. 문자열이 주어진다면 그 문자열의 첫번째 글자를 선택하는 경우와 선택하지 않는 경우의 합으로 표현 하는 것이다. 여기서 중요한것은 end 조건인데, 문자열이 ABC 이고 len이 1이라면 3개중 하나를 뽑는 것인대 이때는 A, B, C가 다 가능하기 때문에 map으로 각각의 글자를 배열로 리턴 해주는 것이다. 이것만 조심하면 간단히 조합코드를 작성 할 수 있다.

solution

어떻게 보면 조금 복잡 할 수 있지만. 가장 바깥에 course.map은 course가 [3,4,5] 라면 3개의 메뉴로 구성된 코스 4개의 메뉴로 구성된 코스 이렇게 각각 가능한 경우를 구하기 위해 감싸놓은 것인고 우리는 course가 3일때를 기준으로 생각해보자. 즉 num이 3인 경우인것이다.

        let counts = orders
            .map { combination($0, len: num) }


orders
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"] 

---->

counts
[["CDE", "BDE", "BCD", "BCE", "ADE", "ACD", "ACE", "ABC", "ABD", "ABE"], 
[], 
[], 
["ADE"], 
["XYZ"], 
["XYZ"], 
["ACD"]]

먼저 이 줄을 살펴 보자, orders는 손님 String의 배열인데 하나의 String은 손님한명의 주문 내역이다. 즉 손님의 주문한 내역을 가지고 3개의 메뉴로 조합을 구성한 것이다. 2개의 메뉴를 주문한 손님2,3은 빈 배열이 나오고 손님1은 5C3 = 10 10개의 경우가 나온 것을 확인 할 수 있다.

        let counts1 = orders
            .map { combination($0, len: num) }
            .flatMap { $0 }

counts
[["CDE", "BDE", "BCD", "BCE", "ADE", "ACD", "ACE", "ABC", "ABD", "ABE"], 
[], 
[], 
["ADE"], 
["XYZ"], 
["XYZ"], 
["ACD"]]

---->
counts
["CDE", "BDE", "BCD", "BCE", "ADE", "ACD", "ACE", "ABC", "ABD", "ABE", "ADE", "XYZ", "XYZ", "ACD"]

위에서 2차원 배열이였던 데이터를 flatmap을 통해 1차원 배열로 변형시킨 것이다. 이부분은 reduce([]) { $0 + $1 }로 구현가능하다.

        let counts1 = orders
            .map { combination($0, len: num) }
            .flatMap { $0 }
            .reduce(into: [:], { counts, word in
                counts[word, default: 0] += 1
            })

counts
["CDE", "BDE", "BCD", "BCE", "ADE", "ACD", "ACE", "ABC", "ABD", "ABE", "ADE", "XYZ", "XYZ", "ACD"]
---->
counts
["ADE": 2, "ABD": 1, "BDE": 1, "BCD": 1, "ABC": 1, "ACD": 2, "ABE": 1, "BCE": 1, "ACE": 1, "XYZ": 2, "CDE": 1]

dictionary의 default값을 통해 각각의 word의 갯수를 카운팅해주는 코드이다. 즉 얼마나 많은 사람이 주문했는지 확인 해보기 위해 중복 체크를 한것이다. 

        guard let max = counts.values.max(), max >= 2
        else { return [] }
        let keys = counts.filter { $0.value == max }
            .map { $0.key }
        return keys

그후 counts의 max값을 구한 후 그 max값을 리턴 해주는 코드이다. 이것을 최종적으로 다 합쳐서 정렬해서 반환 하면 끝!