프로그래머스 [Lv. 3] 불량 사용자 Python

문제 링크

2019 카카오 개발자 겨울 인턴십

코딩테스트 연습 | 프로그래머스 스쿨

정답 코드

def solution(user_id, banned_id):
    lenU = len(user_id)
    lenB = len(banned_id)
    dictionary = dict()
    for ban in banned_id:
        dictionary[ban] = []
    
    def dfs(s, userId, cnt, tmp, length, idx):
        if s == length:
            if dictionary.get(tmp) or dictionary.get(tmp) == []:
                dictionary[tmp].append((idx, userId))
            return
        dfs(s+1, userId, cnt+1, tmp+userId[s], length, idx)
        dfs(s+1, userId, cnt+1, tmp+"*", length, idx)
    
    for idx in range(lenU):
        userId = user_id[idx]
        dfs(0, userId, 0, "", len(userId), idx)
        
    setResult = set()
    def dfs2(s, v, lenB):
        if s == lenB:
            setV = set(v)
            if len(setV) == lenB:
                tmp = sorted(list(setV))
                setResult.add(tuple(tmp))
            return
        for jdx, nextB in dictionary[banned_id[s]]:
            if visited[jdx]:
                continue
            visited[jdx] = 1
            dfs2(s+1, v+[nextB], lenB)
            visited[jdx] = 0
    visited = [0 for _ in range(lenU)]
    dfs2(0, [], lenB)
    answer = len(setResult)
    return answer

풀이 방법

- 우선 이 문제를 풀기 전에 프로그래머스 Lv2 순위 검색을 먼저 풀어 보고 오길 바란다.

    - https://school.programmers.co.kr/learn/courses/30/lessons/72412

프로그래머스

1. 먼저 딕셔너리를 사용할 수 있어야 한다.

    - banned_id에 해당하는 아이디 조합을 만든다음에 list에 append해준다.

2. 한 번 더 dfs를 사용해야하는데 이제는 순열을 구해야한다.

    - 처음에는 냅다 set에 넣어서 계산했기에 testCase의 몇 번 째인지 모르겠지만 8800ms가 나왔다.

    - visited함수를 활용해서 이미 순열에 사용한 id는 배제해줬다.

3. 결과적으로 8800ms도  180ms정도로 최적화에 성공했다.

느낀점

 이제는 아마추어가 아니니까 시간복잡도를 적극적으로 해결할 생각을 해야하고 조합이나 순열에 대해서는 틀려서는 안된다고 생각한다. 개인적으로 백준의 n과 m을 푸는 것도 좋지만 그냥 냅다 많이 푸는 것도 좋다고 본다. itertools사용도 좋지만 나는 최대한 if와 for문만을 사용해서 문제를 풀어볼 생각이다.