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

https://school.programmers.co.kr/learn/courses/30/lessons/72411

✍️ 첫번째 접근

orders를 이중 for문 돌려서 두 order의 교집합을 구해 그 교집합의 개수가 course보다 크거나 같다면 해당 교집합의 조합을 구해 그 조합들 중 가장 많이 나온 조합을 answer 배열에 넣는다.
하지만, 이는 논리가 부족하여 틀리게 되었다.
시간이 지난 후 코드를 보는 지금, 왜 이렇게 짰는지 필자도 이해가 되지 않는다..

import Foundation

func findMax(_ arr: [String]) -> [String] {
    var dict: [String: Int] = [:]
    var strArr: [String] = []
    for i in arr {
        if dict[i] == nil {
            dict[i] = 1
        }
        else {
            dict[i]! += 1
        }
    }
    var sortedDict = dict.sorted { $0.value > $1.value }
    var val = sortedDict.first?.value ?? 0
    for i in sortedDict {
        if i.value != val {
            break
        }
        strArr.append(i.key)
    }
    return strArr
}

func intersection(_ str1: String, _ str2: String) -> String {
    var str: String = ""
    var intersectionStr: String = ""
    for i in str1 {
        if !str.contains(String(i)) {
            str += String(i)
        }
    }
    for i in str2 {
        if str.contains(String(i)) {
            intersectionStr += String(i)
        }
    }
    return intersectionStr
}

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    
    // 조합
    var combiArr: [String] = []
    func combination(_ target:[String], _ target_num: Int, _ index: Int,_ tmp:[String]){
        if tmp.count == target_num{
            combiArr.append(tmp.joined(separator: ""))
            return
        }

        for i in index ..< target.count{
            combination(target, target_num, i+1, tmp + [target[i]])
        }
    }    
    var answer: [String] = []
    var orders = orders
    orders.sort { $0.count < $1.count } // order의 크기별 오름차순으로 정렬
    for c in course {
        var arr: [String] = []
        for i in 0..<orders.count-1 {
            if orders[i].count < c {    // order이 course보다 작으면 애초에 만족하지 않으므로
                continue
            }
            for j in i+1..<orders.count {
                var intersectionStr = intersection(orders[i],orders[j])   // 비교하는 두 order의 교집합
                if intersectionStr.count >= c {
                    combination(intersectionStr.map { String($0) } , c, 0, [])
                }
                
            }
        }
        var maxs = findMax(combiArr)
        answer += maxs
        combiArr = []
    }
    answer.sort { $0 < $1 }
    
    return answer
}

✍️ 두번째 접근

orders를 이중 for문 돌리는데 두 order의 교집합을 구하는 것이 아니라 두 order 각각 조합을 구한 후에 서로 포함되는지 여부를 따진 후에 해당 조합 중 가장 많이 등장한 조합을 answer 배열에 넣음으로써 문제를 해결하였다.

// 조합 뺑뺑이 돌리면 될 듯
import Foundation

func findMax(_ arr: [String]) -> [String] {
    var dict: [String: Int] = [:]
    var strArr: [String] = []
    for i in arr {
        if dict[i] == nil {
            dict[i] = 1
        }
        else {
            dict[i]! += 1
        }
    }
    var sortedDict = dict.sorted { $0.value > $1.value }
    var val = sortedDict.first?.value ?? 0
    for i in sortedDict {
        if i.value != val {
            break
        }
        strArr.append(i.key)
    }
    return strArr
}

func solution(_ orders:[String], _ course:[Int]) -> [String] {
    var answer: [String] = []
    var orders = orders
    for i in 0..<orders.count {
        orders[i] = String(orders[i].sorted())
    }
    // 조합
    func combination(_ target:[String], _ target_num: Int, _ index: Int, _ tmp:[String], _ combi: inout [String]){
        if tmp.count == target_num{
            combi.append(tmp.joined(separator: ""))
            return
        }

        for i in index ..< target.count{
            combination(target, target_num, i+1, tmp + [target[i]], &combi)
        }
    }
    for c in course {
        var arr: [String] = []
        for i in 0..<orders.count-1 {
            if orders[i].count < c {  // order이 course보다 작으면 애초에 만족하지 않으므로
                continue
            }
            var combiArr1: [String] = []
            combination(orders[i].map { String($0) },c,0,[], &combiArr1)
            for j in i+1..<orders.count {
                var combiArr2: [String] = []
                combination(orders[j].map { String($0) },c,0,[],&combiArr2)
                for k in combiArr2 {
                    if combiArr1.contains(k) {
                        arr.append(k)
                    }
                }
            }
        }
        var maxArr = findMax(arr)
        answer+=maxArr
    }
    return answer.sorted { $0 < $1 }
}