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

요구능력

조합 + 해시

 

문제풀이

DFS를 활용해서 조합을 사용하였고, 문제에서도 조합이라고 했기 때문에 음식의 순서는 상관없다.

그래서 sorTemp변수를 사용해서 얻어오는 조합마다 정렬해서 받았다.

이 부분이 이 문제의 변별력인것 같다.

ex) XY, YX는 같은 음식조합이다.

 

그리고 사실 "만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다."

이 부분을 안읽고 문제를 풀다가 가 예제 2번에 AB는 왜 안되지라는 생각을 계속했는데,

2가지 메뉴구성 중에서도 가장 많이 함께 주문된 메뉴구성을 골라야했다.

가장 많이 함께 주문된 메뉴구성을 안고르고 그냥 course의 개수에 맞고 2개이상인 메뉴구성을 계속 고르다보니 문제가 안풀렸던것이다.

 

후기

문제의 조건을 잘 읽는지 판단하는문제같다.

 

코드

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

    //조합
    var visited = Array(repeating: false, count: 11) //조합을 위한 방문여부
    var temp = "" //문자열 조합에 사용할 프로퍼티
    var dict = [String:Int]() //문자열: 조합된 횟수
    
    //dfs를 활용한 조합
    func dfs(_ order: [String], _ depth: Int, _ start: Int){
        if depth >= 2{ //문자열이 2개이상 모이면
            let sorTemp = String(temp.sorted()) //문자열 정렬(문제의 메뉴구성이 순열이아닌 조합으로 판단해야됨)
            if dict[sorTemp] == nil{ //아직 dict의 Key가 아직없다면
                dict[sorTemp] = 1
            }else{
                dict[sorTemp]! += 1
            }
        }
        
        for i in start..<order.count{
            if !visited[i]{
                visited[i] = true
                temp += "\(order[i])"
                dfs(order, depth + 1, i)
                visited[i] = false
                temp.removeLast()
            }
        }
    }
    
    //주문목록에있는 모든경우를 dfs에서 조합해본다.
    for i in 0..<orders.count{
        let arr = orders[i].map{String($0)}
        dfs(arr, 0, 0)
    }
    var result = [String]() //결과값 저장할 프로퍼티
    var keycountValue = [Int:Int]() //키의개수 : 개수의 최대값
    
    //0으로 초기화
    for i in course{
        keycountValue[i] = 0
    }
    
    //course에서 원하는 갯수라면 키의개수당 최대값을 갱신
    for (key, value) in dict{
        if course.contains(key.count){
            keycountValue[key.count] = max(keycountValue[key.count]!, value)
        }
    }
    
    //동일한키의개수의 최대값을 가진 key이고, 문제에서 말한 최소2명이상이라면 result에추가
    for (key,value) in dict{
        if value == keycountValue[key.count] && value >= 2{
            result.append(key)
        }
    }
    
    result.sort()
    return result
}