[python] programmers - 불량 사용자

오늘은 프로그래머스의

불량 사용자라는 문제를 들고 왔다.

 

개인적으로 카카오 알고리즘이

생각해볼거리가 많아서

생각의 폭을 넓히는데 좋은 거 같다.

 

문제 링크는 여기로

궁금하신 분들은 들어가서 확인해보면 좋을 것 같다.

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

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

 

1. 아이디어

 

문제 자체는 완전 탐색을 사용하여 풀었다.

제재 아이디 리스트를 돌면서

가능한 모든 방법을 탐색해보는 방법으로

 

중복을 제거하기 위해

set()을 사용했다.

 

자세한 설명은 코드와 함께 첨부하겠다.

 

2. 코디 작성

# 중복 정답을 제거하기 위해 set사용
answer_set = set()
 
def solution(user_id, banned_id):
 
    # visited 체크. 사용자가 불량 사용자로 체크 되었는지를 idx로 확인
    checked = [0] * len(user_id)
    
    # 불량 사용자 확인
    def find_user(num, i):
        
        global answer_set
    
        # 만일 불량 사용자를 다 찾았다면
        if num == len(banned_id):
            # checked의 값을 문자열로 저장해 set에 add
            ans = "".join(map(str, checked))
            answer_set.add(ans)
            return
 
        # 만일 인덱스 위치를 벗어난다면 return
        if i > len(banned_id)-1:
            return
        
        # 이번에 찾을 제재 아이디
        ban_id = banned_id[i]
        
        # 유저를 돌며
        for k in range(len(user_id)):
            # 아직 제재 리스트에 추가되지 않고
            if checked[k]:
                continue
            # 제재 아이디와 유저의 이름의 길이가 다르지 않은 사용자 중에서
            if len(ban_id) != len(user_id[k]):
                continue
            t = 0
            correct = True
            # 별을 제외하고 다른 문자가 겹치는지를 확인
            while t < len(ban_id):
 
                if ban_id[t] == '*':
                    t += 1
                    continue
 
                if ban_id[t] != user_id[k][t]:
                    correct = False
                    break
 
                t += 1
 
            # 만일 가능한 사용자라면
            if correct:
                # 체크리스트에 표기해서
                checked[k] = 1
                # 다음 제재 아이디를 확인
                find_user(num+1, i+1)
                # 체크리스트는 원래로 돌리기
                checked[k] = 0
    
    find_user(0, 0)
    
    return len(answer_set)