[알고리즘 연습] 불량 사용자 (프로그래머스 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를 한번쯤 고려해보자.