[programmers] 프로그래머스 불량 사용자(Python)

(주)그렙

[programmers] 프로그래머스 불량 사용자

(Python)

(글쓴날 : 2020.05.10)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 불량 사용자

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

---

2) 풀이 과정

* 시간 복잡도 : O(2ⁿ)

 

응모자 아이디 문자열과 일부 문자가 *로 표시되어 있는 불량 사용자 문자열이 주어질 때, 서로 일치할 가능성이 있는 문자열 집합의 경우의 수를 구하는 문제입니다.

 

저의 경우, DFS를 적용하였으며, Python을 사용했습니다.

일종의 백트래킹 형태로 탐색해가며 만약, 응모자 아이디 문자열과 불량 사용자 문자열이 일치할 시 스택에 저장해, 모든 불량 사용자 문자열을 찾아낸 뒤, 중복을 제거하여 제재 아이디가 될 수 있는 총 경우의 수를 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

def DFS(sj, user_id, banned_id, visit_u, visit_b, stack):
    if len(set(stack)) == len(banned_id):
        answer.append(stack[:])
        return
    
    for i in range(len(user_id)):
        for j in range(sj, len(banned_id)):
            if not visit_u[i] and not visit_b[j] :
                length_ui = len(user_id[i])
                length_bi = len(banned_id[j])
                
                if length_ui != length_bi:
                    continue
                
                isSame = True
                for k in range(length_ui):
                    if user_id[i][k] != banned_id[j][k]:
                        if banned_id[j][k] != "*":
                            isSame = False
                            break
                
                if isSame:
                    visit_b[j] = visit_u[i] = True
                    stack.append(user_id[i])
                    DFS(j, user_id, banned_id, visit_u, visit_b, stack)
                    visit_b[j] = visit_u[i] = False
                    stack.pop()
 
                    
def solution(user_id, banned_id):
    global answer
    answer = []
    visit_u = [False] * len(user_id)
    visit_b = [False] * len(banned_id)
    stack = []
    
    DFS(0, user_id, banned_id, visit_u, visit_b, stack)
    
    return len(list(set([tuple(sorted(ans)) for ans in answer])))

---