[알고리즘 연습] 불량 사용자 (프로그래머스 lv3, 스위프트)

문제

https://programmers.co.kr/learn/courses/30/lessons/64064

코딩테스트 연습 - 불량 사용자

풀이

import Foundation

func solution(_ user_id:[String], _ banned_id:[String]) -> Int {
    var bannedList = [[String]]()

    // 각 banned id 별로 후보군 생성
    for bid in banned_id {
        var temp = [String]()
        var bidarr = Array(bid).map { String($0) }

        for uid in user_id {
            var uidarr = Array(uid).map { String($0) }

            if bid.count != uid.count { continue } 
            var possible = true
            for i in 0..<bid.count {
                if bidarr[i] == "*" { continue }
                if bidarr[i] != uidarr[i] {
                    possible.toggle()
                    break
                }
            }
            if possible { temp.append(uid) }
        }
        bannedList.append(temp)
    }

    // dfs로 가능한 케이스 탐색
    // queue를 구현해서 bfs로 구현해도됨    
    var stack = [(idx: Int, idList: [String])]()
    var answer = [[String]]()

    // 먼저 첫번째 banned id 후보들을 stack에 넣어줌
    for id in bannedList[0] {
        stack.append((0, [id]))
    }

    while stack.count > 0 {
        let now = stack.removeLast()

        // 만약 현재의 idx가 마지막이라면 answer에 해당값을 넣어줌
        if now.idx == banned_id.count-1 {
            answer.append(now.idList)
            continue
        }

        let idx = now.idx + 1

        // 다음 idx에서 가능한 것을 추가해서 stack에 추가
        for id in bannedList[idx] {
            var idList = now.idList
            if idList.contains(id) { continue } // 이미 포함시켜준값이라면 skip
            idList.append(id)
            stack.append((idx, idList))
        }
    }

    // 최종값은 중복이 없어야하며 순서를 고려하지 않아야함
    // 중복을 없애기 위해 Set를, 순서를 고려하지 않기 위해 모두 sort처리
    return Set(answer.map { $0.sorted() }).count
}

• dfs/bfs 문제라는 것을 파악하기 어려웠다. 예전에 파이썬으로 풀었을 때는 product를 사용했는데 dfs/bfs를 사용하는 것이 더 직관적인 것 같다.
• 여러 경우의 수를 탐색하는 경우라면 dfs/bfs를 한번쯤 고려해보자.