불량사용자 python(카카오 2019겨울인턴십)[프로그래머스]

문제 주소입니다.

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

프로그래머스

---

1. 문제 설명

2. 문제 해석

3. 소스 코드

4. 결과

---

1. 문제 설명

개발팀 내에서 이벤트 개발을 담당하고 있는 무지는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 프로도 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다. 무지와 프로도는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다. 예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면 ["frodo", "fradi", "crodo", "abc123", "frodoc"] 다음과 같이 불량 사용자 아이디 목록이 전달된 경우, ["fr*d*", "abc1**"] 불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다. [frodo, abc123], [fradi, abc123] 이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

제한사항

user_id 배열의 크기는 1 이상 8 이하입니다. user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다. 응모한 사용자 아이디들은 서로 중복되지 않습니다. 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다. banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다. banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다. 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다. 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다. 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다. 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

예시

입출력 예

 

user_id	banned_id	result
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["fr*d*", "abc1**"]	2
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["*rodo", "*rodo", "******"]	2
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["fr*d*", "*rodo", "******", "******"]	3

---

2. 문제풀이

문제의 범위가 크지 않아서 dfs를 이용하여 모든 경우의 수를 체크 유저와 벤유저를 사용했는지 확인하는 리스트 변수를 만들어 체크하면서 진행 set구조를 이용하여 중복을 없애고 길이를 리턴함으로써 경우의 수 반환.

 

---

3. 소스코드

#Lv3 카카오 2019 인턴십 불량이용자
 
def solution(user_id, banned_id):
    answer = set()
    ban_length = len(banned_id)
    user_length = len(user_id)
    #벤길이과 유저길이가 같다면 경우의 수는 1개라고 리턴
    if ban_length == user_length:
        return 1
    #걸린 유저 체크용
    use_user = [1 for _ in range(user_length)]
    #사용된 벤유저 체크용
    use_ban = [1 for _ in range(ban_length)]
    #dfs를 이용하여 경우의 수를 검사
    stack = []
    #첫 시작은 0부터이다.
    stack.append([0, use_user, use_ban])
    #스택이 빌때까지 반복
    while stack:
        #스택에서 데이터를 꺼내 매칭
        idx, use_user, use_ban = stack.pop()
        #모든 벤유저를 찾았다면 정답에 추가
        #중복을 방지하기 위해 셋구조에 추가
        if idx == ban_length:
            temp = []
            for i in range(user_length):
                if not use_user[i]: temp.append(user_id[i])
            if temp: answer.add(tuple(temp))
        #벤유저와 모든 유저를 반복해서 돈다.
        for i in range(ban_length):
            #체크한 벤유저가 아니라면
            if use_ban[i] : 
                for j in range(user_length):
                    # 사용한 유저가 아니어야 하고, 벤유저아이디 길어와 유저아이디 길이가 같아야 한다.
                    if use_user[j] and len(banned_id[i]) == len(user_id[j]):
                        #반복문을 돌면서 둘이 매칭되는지 확인한다. * 인경우 넘어간다.
                        for k in range(len(user_id[j])):
                            if user_id[j][k] != banned_id[i][k] and banned_id[i][k] != '*':
                                break
                        #break가 걸리지 않았다면
                        else:
                            #유저와 벤유저 모드 체크하고
                            use_user[j] = 0
                            use_ban[i] = 0
                            #스택에 추가한다.
                            stack.append([idx+1, use_user[:], use_ban[:]])
                            #체크한것을 해제
                            use_user[j] = 1
                            use_ban[i] = 1
    #set의 길이가 경우의 수이다.
    return len(answer)
 
    
users_id = [
    ["frodo", "fradi", "crodo", "abc123", "frodoc"],
    ["frodo", "fradi", "crodo", "abc123", "frodoc"],
    ["frodo", "fradi", "crodo", "abc123", "frodoc"]
]
 
banned_id = [
    ["fr*d*", "abc1**"],
    ["*rodo", "*rodo", "******"],
    ["fr*d*", "*rodo", "******", "******"]
]
 
result = [2, 2, 3]
 
for i in range(3):
    answer = solution(users_id[i], banned_id[i])
    if answer == result[i]:
        print('정답')
    else:
        print('틀림')

 

 

---

4. 결과