프로그래머스 - 메뉴리뉴얼

programmers.co.kr/learn/courses/30/lessons/72411?language=swift

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

아직까지 알고리즘 푸는 기술이 너무너무 부족하단 걸 문제를 풀때마다 느낀다.

한 문제에 몇시간씩 걸리니 ㅠㅠ

근데 이제 조금씩 어떤문제를 보면 이렇게 풀어보면 되겠다는 게 보이니까 조금 더 노력할 마음도 생긴다

 

문제를 보고 dfs로 모든 경우를 탐색해서 풀어봐야 겠다고 생각하고

일단 계속 반복해서 모든 경우의 수를 구했다.

 

그리고 그 경우의 수를 조건에 맞게 필터링을 해주었다

1. 조건은 입력받은 course갯수와 같아야 하고, 주문은 1번 이상 들어와야한다

2. 1번 조건을 맞춘 메뉴중 주문이 가장 많은 순서만 뽑아냄 만약 최대값이 같다면 전부 다

 

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

	//모든 경우의 수를 구하기위해 방문여부를 확인할 visit배열을 만들어줌
    for order in orders {
        let visit = Array(repeating: false, count: order.count)
        dfs(visited: visit, menu: "", characters: order.sorted(), result: &result)
    }
    
    var answer = [String]()
    course.forEach { (course) in
    	//1번 조건: 코스요리 갯수중 하나이면서 1번 이상 주문된 메뉴조합
        let newMenu = result.filter { $0.key.count == course && $0.value > 1}
        //2번 조건: 1번을 만족하고 제일 많이 주문된 메뉴
        answer.append(contentsOf: newMenu.filter { $0.value == newMenu.values.max() }.map { $0.key })
    }
    
    //오름차순 정렬
    return answer.sorted()
}

func dfs(visited: [Bool], menu: String, characters: [Character], result: inout [String: Int]) {
    var temp_visited = visited
    
    //메뉴를 result배열에 담아줌, 최초 조합된 메뉴라면 1로 값을 지정하고, 아니면 +1
    if result[menu] == nil {
        result.updateValue(1, forKey: menu)
    } else {
        result.updateValue(result[menu]! + 1, forKey: menu)
    }
    
    //계속 모든 경우를 찾을때까지 반복
    for i in 0 ... visited.count - 1 {
        guard visited[i] == false else { continue }
        temp_visited[i] = true
        dfs(visited: temp_visited, menu: "\(menu)\(characters[i])", characters: characters, result: &result)
    }
}