[2019 카카오 개발자 겨울 인턴십] 불량 사용자

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

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

def change_v_to_bit(v):
    bit = ""
    for i in range(len(v)):
        bit += str(v[i])
    return bit

def is_in(bit):
    global result
    if bit in result:
        return True
    return False

def match(ban,user):
    if len(ban) != len(user):
        return False
    for i in range(len(ban)):
        if ban[i] == "*":
            continue
        else:
            if ban[i] != user[i]:
                return False
    return True

def dfs(user_id, banned_id,n,v):
    global result
    answer = 0
    if n == len(banned_id):
        bit = change_v_to_bit(v)
        if not is_in(bit):
            result.add(bit)
            return 1
        return 0
    
    target = banned_id[n]
    for i in range(len(user_id)):
        if v[i]:
            continue
        if match(target,user_id[i]):
            v[i] = 1
            answer += dfs(user_id,banned_id,n+1,v)
            v[i] = 0 
    
    return answer


result = set()

def solution(user_id, banned_id):
    global result

    visited = [0]*len(user_id)

    cnt = dfs(user_id, banned_id,0,visited)

    return cnt
    

풀이

가능한 모든 '조합'을 구하는게 문제의 정답이다.

조합을 구하기 위해 백트래킹을 사용해서 완전 탐색했다.

 

user_id 크기의 visited 배열을 만들고 사용한 user_id 에 해당하는 인덱스를 방문처리했다.

banned_id 만큼 user_id를 찾았으면 하나의 조합이 완성된 것이므로 카운트 해준다.

 

순서만 바뀐 같은 조합을 카운트하지 않기 위해 set 자료구조에 결과를 저장했다.

저장할 때 visited 요소를 string으로 변환해 저장해 주었다. 

이걸 이진수로 계산해 저장하면 비트마스킹 기법인데(00011 -> 3으로 저장하는 느낌) 최적화를 할때 사용하면 좋다. (이 문제에선 사용하지 않았다.)

 

시간복잡도

user_id 배열의 길이 가 N

user_id 이름길이가 M

banned_id 의 배열의 길이가 L(B<=N) 이라고 했을 때

 

dfs 함수를 보면 for문으로 N번 호출하고

호출할때마다 match를 통해 user_id길이를 O(M) 시간을 들여 검사한다.

 

그리고 그 dfs의 스택 깊이가 최대 L 이다.

즉 O(NML) 이다.