[프로그래머스] 메뉴 리뉴얼

문제

프로그래머스

입력

orders: [String] = 손님들이 시킨 단품메뉴 리스트, 대문자로 제공 ex) ["ABC", "DEF"]

course: [Int] = 만들고 싶은 단품메뉴 개수
ex) [2,3,4]면 단품 메뉴 개수가 2개, 3개, 4개 조합의 세트 메뉴를 만들기를 원하는 것

 

결과

result: [String]

각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.

배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.

만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

 

해석

먼저 ABCD를 주문했으고 course = [2,3]이면 나올 수 있는 조합은 [AB, AC, AD, ABC, BCD] 이다

즉, 한 주문에서 course에 따라 무궁무진하게 나올 수 있다. 

 

1. 각 주문에대한 모든 조합을 구해야한다. 

2. 각 조합에 대해서 몇번 주문되어있는지 count한다.

3. count를 기준으로 내림차순 정렬하여 가장 주문이 많이된걸 앞으로 배치한다.

4. 세트 조합길이마다 최대 주문횟수를 기록하며 최대주문 횟수에 해당되는 메뉴만 담아준다.

 

import Foundation

extension String {
    subscript(_ index: Int) -> String {
        String(self[self.index(self.startIndex, offsetBy: index)])
    }
}

func combination(_ elements: String, _ k: Int) -> [String] {
    var result = [String]()
    
    func combi(_ index: Int, _ now: String) {
        if now.count == k {
            result.append(now)
            return
        }
        
        for i in index..<elements.count {
            combi(i + 1, now + elements[i])
        }
    }
    combi(0, "")
    
    return result
}

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    
    var allCase: [String] = []
    
    for order in orders {
        for limit in course {
            let cases =  combination(order, limit)
            allCase.append(contentsOf:cases)
        }
    }

    // cource 개수에 맞게 모든 조합을 뽑아낸다. 
    
    var countDict: [String: Int] = [:] // 메뉴조합 : 주문한 수 
    
    allCase.forEach {
        let key = String($0.sorted()) // AB == BA 같아야하므로 키를 사용하기전에 정렬 후 사용
        countDict[key, default:0] += 1 // 메뉴 주문 횟수를 카운팅한다.
    }
    
   let sortedArray  = (countDict.sorted(by: { $0.value == $1.value ? $0.key < $1.key : $0.value > $1.value })) // 메뉴 언급 횟수를 최우선으로 정렬하고 만약 같다면 메뉴이름을 오름차순으로 정렬 

    var maxLengthDict: [Int: Int] = [:] // 단품메뉴 개수 : 가장 높은 주문 횟수 

    var ans: [String] = []

    for info in sortedArray {
        let key = info.key
        let value = info.value
        
        if value < 2 { // 최소주문은 2번 이상이므로 
            continue
        }
        
        if let max =  maxLengthDict[key.count] { //단품메뉴 개수의 주문횟수가 이미 있다면
            if max == info.value { // 주문횟수가 같아야만 추가가능
                ans.append(key)
            }

        } else { // 해당 단품 메뉴 최대 주문횟수 초기화 
            maxLengthDict[key.count] = info.value
            ans.append(key)
        }
    }    
    
    return ans.sorted() // 문자열 오름차순
}