[Programmers] 2021 KAKAO BLIND RECRUITMENT - 메뉴 리뉴얼

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

A-Z까지의 알파벳이 조합된 메뉴들이 배열로 입력되고, 각 메뉴들에 대해서 가능한 조합들 중 가장 많이 주문된 조합을 선택하는 문제입니다.

예를 들어 ["ABC", "ACD"]가 들어왔다면

"ABC" -> ["A", "AB", "ABC", "AC", "B", "BC", "C"]

"ACD" -> ["A", "AC", "ACD", "AD", "C", "CD", "D"]

-> [A : 2, AB : 1, ABC : 1, AC : 2, ACD : 1, AD : 1, B : 1, BC : 1, C: 2, CD : 1, D : 1] 가 총 주문 조합 수가되고, 이 중 조합의 갯수(course)를 원하는 것을 찾는데, 

course = [2]라고 한다면

AB, AC, AD, BC, CD 중 가장 많이 주문한 것을 찾아서 반환하는 것입니다.

course는 오름차순으로 정렬되어있다고 제한사항에 주어져있으며, course는 2 ~ 10의 Int값을 갖고있는 배열입니다. 결과값 또한 오름차순으로 정렬되어야 합니다. 또한 주문 조합의 총 값이 같을 경우(ex AB가 2이고 BC가 2인 경우, 2가 최대값인 상황) 해당 값들을 모두 포함하게 하면 됩니다.

import Foundation
func solution(_ orders:[String], _ course:[Int]) -> [String] {
    let menuList = sortedOrders(orders: orders)
    print("Check menus : \(menuList)")
    var result: [String] = []
    let allCombinations = menuList.allCombination.map {
        $0.sorted().joined(separator: "") // 모든 조합 찾음...
    }
    
    for courseCount in course {
        let combines = allCombinations.filter {
            $0.count == courseCount // 모든 조합 중에서 count에 해당하는 값들만 모음
        }
        result += orderContainList(orders: orders, combineList: combines)
    }
    
    return result.sorted()
}

func orderContainList(orders: [String], combineList: [String]) -> [String] {
    var countDict: [String: Int] = [:]
    for order in orders {
        let _order = [order] // 주문 한 것 중의 경우의 수 찾기 위함
        let orderCombine = sortedOrders(orders: _order).allCombination.map { $0.sorted().joined(separator: "") }.filter{ (element) -> Bool in
                return combineList.contains { (combineElement) -> Bool in
                    return element.elementsEqual(combineElement)
                }
            }
        orderCombine.forEach { (element) in
            if let v = countDict[element]{
                countDict[element] = v + 1
            }else {
                countDict[element] = 1
            }
        }
    }
    return mostManyCount(dict: countDict)
}

func mostManyCount(dict: [String: Int]) -> [String] {
    var returnArr : [String] = []
    for element in dict {
        guard element.value > 1 else {
            continue
        }
        if returnArr.isEmpty {
            returnArr.append(element.key)
        }else {
            guard let _value = dict[returnArr.first!] else {
                continue
            }
            if element.value > _value {
                returnArr.removeAll()
                returnArr.append(element.key)
            }
            else if element.value == _value {
                returnArr.append(element.key)
            }else{
                //do nothing
            }
        }
    }
    
    return returnArr
}

// 메뉴의 종류 정리하는 부분
func sortedOrders(orders: [String]) -> [String] {
    var returnOrders = [String]()
    /*
    for element in orders {
        element.forEach {
            if !returnOrders.contains(String($0)) {
                returnOrders.append(String($0))
            }
        }
    }
    */
    var _orders = orders
    while !_orders.isEmpty {
        if let first = _orders.first {
            first.forEach { (element) in
                if !returnOrders.contains(String(element)) {
                    returnOrders.append(String(element))
                }
            }
            _orders.removeFirst()
        }
    }
    return returnOrders.sorted()
}

extension Array {
    //https://stackoverflow.com/questions/39160552/find-all-combination-of-string-array-in-swift
    var allCombination: [[Element]] {
        guard count > 0 else {
            return [[]]
        }
        let tail = Array(self[1..<endIndex])
        
        let head = self[0]
        
        let withoutHead = tail.allCombination
        
        let withHead = withoutHead.map { $0 + [head] }
        
        return withHead + withoutHead
    }
}

print(solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH", "ABCDEFGH"], [2, 3, 4]))//["AC", "ACDE", "BCFG", "CDE"]

이 코드는 시간 복잡도를 생각하지 않고 구현한 코드입니다.

결과값은 정상적으로 나오지만, programmers에서 제출 후 채점하기를 실행하면 Timeout 결과가 나옵니다.(20개중 8개가 타임 아웃)

그럼 당연히 최적화를 시켜야겠죠.

 

이제 이렇게 구현할 겁니다.

1. 각 Orders의 조합의 총 카운트
2. Course에 포함되어있는 Int값과 모든 조합의 메뉴 갯수(String.count)가 동일한 것들을 찾고
3. 찾은 값들 중 카운트가 가장 큰 값들을 모으는 것

func orderCombine(dict: inout [String: Int], course: [Int], index: Int, orderChar: [Character], combineStr: String) {

}

해당 함수를 먼저 만들었습니다.

dict는 조합을 Key로 갖고있는 Dictionary고, orderChar는 orders의 각 element를 sorted()하면 나오는 character의 배열입니다. index는 orderChar의 몇 번째 인덱스부터 탐색할지 알기 위해서 사용하는 매개변수이고 combineStr은 찾은 Character를 뒤에 붙임으로써 조합을 완성하기 위한 값입니다.

func orderCombine(dict: inout [String: Int], course: [Int], index: Int, orderChar: [Character], combineStr: String) {
	guard let lastCourseNum = course.last else {
        //course가 없으면 조합 할 필요가 없다..
        return
    }
    if lastCourseNum < combineStr.count {
        //조합된 String의 길이가 원하는 가장 큰 조합의 갯수보다 클 경우엔 검사할 필요가 없다.
        return
    }
}

원래 문제상에는 course의 크기가 1~10 사이입니다. 즉 최소 1개 이상은 들어있다는 말이니 사실상 guard를 쓸 필요 없이 강제 언래핑(Forced Unwrapping)을 해도 되지만... 제가 병적으로 강제 언래핑을 싫어해서 사용했습니다. course.last! < combineStr.count로 비교하셔도 상관 없습니다.

(Bluetooth 데이터를 이용하는 일을 많이 해보다 보니 데이터 없는 경우 강제 언래핑 덕분에 죽는 경우가 생각보다 자주 발생하다보니...)

가장 처음 문제 제한사항중 하나가 course값은 항상 오름차순이라고 하였기 때문에 course의 가장 마지막 값이 가장 큰 값이라고 생각 할 수 있고, 따라서 그 값보다 combineStr의 길이가 크다면 굳이 실행할 필요가 없기 때문에 6번째 줄의 구문이 들어갑니다.

func orderCombine(dict: inout [String: Int], course: [Int], index: Int, orderChar: [Character], combineStr: String) {
    ...
    if course.contains(combineStr.count) {
        if let v = dict[combineStr] {
            dict[combineStr]! = v + 1
        }else{
            dict[combineStr] = 1
        }
    }
    for i in index ..< orderChar.count {
        guard !combineStr.contains(orderChar[i]) else {
            continue
        }
        let str = String(orderChar[i])
        orderCombine(dict: &dict, course: course, index: i + 1, orderChar: orderChar, combineStr: combineStr + str)
    }
    ...
}

combineStr의 길이가 course에 들어있는 Int와 동일한 것이 있는 경우에 전체 갯수를 확인하기 위해 dict에 combineStr을 Key값으로 하여 value를 저장합니다.

그 후 현재 탐색중인 index 값부터 orderChar의 전체 길이만큼 탐색을 합니다. 그리고 재귀로 다시 orderCombine을 호출합니다. 이 때 index 파라미터에는 i + 1값을 넣는데, 이 이유는 현재 탐색중인 index의 다음부터 찾기 위함입니다.

이제 solution함수를 구현할 차례입니다.

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    var dict: [String: Int] = [:]
    
    //let _course = course.sorted() // 문제에 주어진 내용대로면 항상 오름차순이기 때문에 필요 없다.
    
    //각 주문들에 대한 정렬 시작
    for order in orders {
        let order = order.sorted() // [Character] return
        orderCombine(dict: &dict, course: course, index: 0, orderChar: order, combineStr: "")
    }
}

orders의 각 element에 대해서 for문을 돌리고, element에 대해 sorted()를 실행하면 각 Character로 나뉘어진 오름차순 배열이 반환됩니다([Character]).

그 값을 위에서 구현한 orderCombine을 호출하면서 넣어줍니다. index 파라미터에 0인 이유는 가장 처음 값부터 탐색하기 위함입니다.

func solution(_ orders:[String], _ course:[Int]) -> [String] {
	...
    var returnArr = [String]()
    for element in course {
        let dictFilter = dict.filter { element == $0.key.count && $0.value > 1 } // dict의 key의 길이가 element와 같고, 그 value가 1이상인 값들만 거름
        /*
        let maximumNum = dictFilter.max { (element1, element2) -> Bool in
            print("element1 : \(element1) :: \(element2)") 
            return element1.value < element2.value
        }
        */
        let maximumNum = dictFilter.max { $0.value < $1.value }
        let sortedMenu = dictFilter.filter { maximumNum!.value == $0.value }.map{$0.key} // value가 maximumNum과 같은 것들의 key만 array로 만든다.
        returnArr.append(contentsOf: sortedMenu)
    }
    return returnArr.sorted()
}

orderCombine의 구문이 모두 끝났다면 이제 다음으로 넘어가야 합니다.

dict에 저장된 값은 각 조합을 Key로하는 카운트들이 집계되어있습니다. 이제 그 값을 우리가 원하는 대로 변환해야 합니다.

먼저 solution 함수에서 return되는 값과 동일한 형태인 returnArr이라는 변수를 만듭니다.

그 후 course의 각 값을 이용해서 dict를 필터링합니다. 이 때 비교대상은 dict의 Key의 길이와 course의 element값들이고, 가장 기본적인 사항으로 각 dict의 value는 2 이상이어야 합니다.(문제에 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합 이라고 적혀있기 때문)

그 후 필터링 된 결과값(dictFilter) 중 가장 큰 값을 확인하기 위해서 max를 사용합니다. 이 때 까지는 중복되는 카운트에 대해서는 신경쓰지 않아도 됩니다.

그 다음 dictFilter를 다시 한 번 필터링 하는데, 이 때는 이전에 사용한 max값과 동일한 value를 갖는 값들만 필터링합니다.(sortedMenu)

우리가 필요한 것은 dict에서 이용하는 key값들이기 때문에 sortedMenu값을 새로운 배열로 만들어 주기 위해 map을 이용합니다. 이 때 반환될 값은 sortedMenu의 Key값이기 때문에 .map{ $0.key }라고 작성합니다.

해당 for문이 모두 끝나면 returnArr에는 정렬되지 않은 상태로 결과물이 저장됩니다. 따라서 return 할 때 returnArr.sorted()를 호출하여 배열의 값들이 오름차순으로 정렬되어 반환되도록 합니다.

 

아래는 전체 코드입니다.

import Foundation

func orderCombine(dict: inout [String: Int], course: [Int], index: Int, orderChar: [Character], combineStr: String) {
    guard let lastCourseNum = course.last else {
        //course가 없으면 조합 할 필요가 없다..
        return
    }
    if lastCourseNum < combineStr.count {
        //조합된 String의 길이가 원하는 가장 큰 조합의 갯수보다 클 경우엔 검사할 필요가 없다.
        return
    }
    
    if course.contains(combineStr.count) {
        if let v = dict[combineStr] {
            dict[combineStr]! = v + 1
        }else{
            dict[combineStr] = 1
        }
    }
    for i in index ..< orderChar.count {
        guard !combineStr.contains(orderChar[i]) else {
            continue
        }
        let str = String(orderChar[i])
        orderCombine(dict: &dict, course: course, index: i + 1, orderChar: orderChar, combineStr: combineStr + str)
    }
}
func solution(_ orders:[String], _ course:[Int]) -> [String] {
    var dict: [String: Int] = [:]
    
    //let _course = course.sorted() // 문제에 주어진 내용대로면 항상 오름차순이기 때문에 필요 없다.
    
    //각 주문들에 대한 정렬 시작
    for order in orders {
        let order = order.sorted() // [Character] return
        orderCombine(dict: &dict, course: course, index: 0, orderChar: order, combineStr: "")
    }
    
    var returnArr = [String]()
    for element in course {
        let dictFilter = dict.filter { element == $0.key.count && $0.value > 1 } // dict의 key의 길이가 element와 같고, 그 value가 1이상인 값들만 거름
        /*
        let maximumNum = dictFilter.max { (element1, element2) -> Bool in
            print("element1 : \(element1) :: \(element2)") 
            return element1.value < element2.value
        }
        */
        let maximumNum = dictFilter.max { $0.value < $1.value }
        let sortedMenu = dictFilter.filter { maximumNum!.value == $0.value }.map{$0.key} // value가 maximumNum과 같은 것들의 key만 array로 만든다.
        returnArr.append(contentsOf: sortedMenu)
    }
    return returnArr.sorted()
}

 

가장 처음 구현 할 때는 일단 되게 구현해보자는 생각으로 만들었다보니 시간 복잡도를 생각 안했었고, 두 번째는 최대한 효율적으로 계산하기 위해 생각하고 구현했습니다.

손으로 의사코드를 작성하면서 생각해보니 DFS를 이용하면 되겠구나 했습니다.

BFS로 구현할까 생각도 했지만.. Course의 값이 작고 적으면 상관 없지만 각 원소가 2~10인 것을 생각 해볼 때 10이 들어와있다면 비효율적으로 계산되지 않을까 라는 생각이 들었고, 저장 공간도 따로 필요하니 DFS가 낫겠구나 싶었습니다.