Programmers Lv2) [2021 카카오블라인드] 메뉴 리뉴얼

출처: programmers.co.kr/learn/courses/30/lessons/72411

분류: 조합

---

접근방식

카카오 블라인드 2번 문제였습니다!

주어진 코스의 개수에 해당하는 조합을 모두 찾고 그 중에서 가장 많은 사람이 먹었던 메뉴들을 골라주면 됩니다.
여러 개라면 모두 넣어줍니다.

주어진 입력 범위가 그리 크지 않기 때문에 ( 20(orders) x 10(각 order의 최대 길이 ) x 10(course) x 10(각 course의 최대 길이) = 20000 정도?) 
그냥 다 돌면서 조합을 찾아주고 필터해주면 됩니다.

조합을 찾는 방식은 어렵지않게 찾아볼 수 있습니다 :)

저는 각 코스 문자열의 인덱스를 돌면서
해당 인덱스를 추가해서 재귀,
추가하지 않고 재귀를 돌려서 만들었습니다.

func makeOrder(_ order: [Character], _ courseCount: Int, _ idx: Int, _ making: String, _ newOrders: inout [String]) {
    guard making.count < courseCount else {
        newOrders.append(String(making.sorted()))
        return
    }
    guard idx < order.count else { return }
    
    makeOrder(Array(order), courseCount, idx+1, making, &newOrders)
    makeOrder(Array(order), courseCount, idx+1, making + String(order[idx]), &newOrders)
}

한 가지 주의할 점은 최종 결과들 sort 뿐만 아니라 각 조합을 만들어 추가해줄 때도 sort해서 넣어줘야 합니다.
친절하게 3번 예시에서 걸러주고 있네요.

 

해결방법

import Foundation

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    var resultOrders = [String]()
    
    for courseCount in course {
        var maxCourseCount = 0
        var newOrderTable = [String: Int]()
        
        for order in orders {
            var newOrders = [String]()
            makeOrder(Array(order), courseCount, 0, "", &newOrders)
            for newOrder in newOrders {
                newOrderTable[newOrder, default: 0] += 1
                maxCourseCount = max(maxCourseCount, newOrderTable[newOrder]!)
            }
        }
        
        print(maxCourseCount, newOrderTable)
        if maxCourseCount > 1 {
            resultOrders.append(contentsOf: newOrderTable.filter { $0.value == maxCourseCount }.map { $0.key })
        }
    }
    
    return resultOrders.sorted()
}

func makeOrder(_ order: [Character], _ courseCount: Int, _ idx: Int, _ making: String, _ newOrders: inout [String]) {
    guard making.count < courseCount else {
        newOrders.append(String(making.sorted()))
        return
    }
    guard idx < order.count else { return }
    
    makeOrder(Array(order), courseCount, idx+1, making, &newOrders)
    makeOrder(Array(order), courseCount, idx+1, making + String(order[idx]), &newOrders)
}

 

배운점

다 풀고나면 그렇게 어렵지 않은 문제였는데

왜 이리 오래걸리는 것이냐..............