[코딩테스트] 프로그래머스 - 불량 사용자

1. 아이디어 

▪ 아이디와 제재 아이디를 입력 받았을때 해당 아이디가 제재 대상인지 확인하는 함수 작성 

▪ dfs로 구현

   - i는 현재까지 확인한 불량 사용자 아이디 목록 인덱스

   - i가 불량 사용자 아이디 목록의 길이와 같으면

      - chk 리스트를 정렬하고 하나의 문자열로 합쳐서 rs 리스트에 append -> 추후 중복값을 없애기 위함

   - 아이디 목록에서 아이디를 하나씩 꺼내서 다음을 수행

      - 해당 아이디를 방문하지 않았고, 현재 인덱스의 불량 사용자 아이디와 비교했을때 제재 대상에 해당할 경우

         - 해당 아이디를 방문여부 리스트에 추가하기

         - dfs(i+1) 수행

         - 해당 아이디를 방문여부 리스트에서 제거하기 

   - set 함수를 이용하여 중복되는 값 제거하고 rs의 개수 return

2. 시간복잡도

▪ O(L*(V+E)) = O(L*(M+ MN)) = O(LMN) = 8^3

▪ N: user_id 배열의 크기

▪ M: banned_id 배열의 크기

▪ L: user_id 배열의 원소값 길이

3. 변수

▪ 현재 제재한 아이디를 저장할 리스트(chk): str[]

▪ 제재한 아이디 경우의 수를 기록할 리스트(rs): str[]

Code

def check(user_id, banned_id):
    if len(user_id) != len(banned_id):
        return False
    for i in range(len(banned_id)):
        if banned_id[i] == "*":
            continue
        if user_id[i] != banned_id[i]:
            return False
    return True
 
def solution(user_id, banned_id):
    def dfs(i):
        global chk, rs
        
        if i == len(banned_id):
            rs.append(''.join(sorted(chk)))
            return
        
        for each_user_id in user_id:
            if each_user_id not in chk and check(each_user_id, banned_id[i]) == True:
                chk.append(each_user_id)
                dfs(i+1)
                chk.pop()
            
        
    global chk, rs
    
    chk = []
    rs = []
 
    dfs(0)
    answer = len(set(rs))
 
    return answer

 

프로그래머스