LV3 [KAKAO] 불량 사용자

---

문제

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

프로그래머스

풀이

우선 banned_id 에 있는 리스트를 돌면서, 이 포맷에는 어떤 user_id 들이 들어갈 수 있을지 초기화 했다.

 

예시를 보자면

 

 

객 패턴에 맞는 user_id를 저장했다. 

 

패턴에 매칭되는걸 확인하는건 우선 길이를 먼저 체크했고, *가 아닌 경우에 문자열이 같은지 확인했다.

 

 

이후에는 dfs를 통해서 모든 경우의 수를 만들어보았다.

단, 배열에 중복된 요소는 들어가지 않게 말이다.

 

결과로는

[frodo, crodo, frodoc]

[frodo, crodo, abc123]

[crodo, frodo, frodoc]

[crodo, frodo, abc123]

 

총 4개의 값이 도출된다.

 

단, 이 문제는 순서를 고려하지 않으므로 [frodo, crodo, frodoc] 과 [crodo, frodo, frodoc] 은 같은 값으로 취급해야한다.

 

따라서 값을 정렬한 다음, join을 통해서 문자열로 만들고 set으로 중복을 제거했다.

(정렬하면 두 배열 모두 [crodo, frodo, frodoc] 형태로 되고, join하면 "crodofrodofrodoc"이 될거다. 마지막으로 set에 넣으면 이미 존재하면 추가 되지 않으므로 중복이 자연스레 제거 된다.)

 

그리고 set의 길이를 return 해주면 된다.

 

 

코드

import copy
answer = set()

def dfs(target, i, tempArr, l):
    global answer
    
    if l == len(tempArr):
        tempArr.sort()
        answer.add("".join(tempArr))
        return
    
    if i >= len(target):
        return
    
    for val in target[i]:
        if val not in tempArr:
            tArr = copy.deepcopy(tempArr)
            tArr.append(val)
            dfs(target, i+1, copy.deepcopy(tArr), l)
            
    
def solution(user_id, banned_id):
    global answer
    
    # '*' 에 알파벳 소문자 또는 숫자가 들어갈 수 있다.
    
    target = []
    for banId in banned_id:
        candid = set()        
        for userId in user_id:
            # 매칭되는지 확인한다.
            if len(banId) != len(userId): continue
            
            possible = True
            for i in range(len(userId)):
                if banId[i] != '*' and (userId[i] != banId[i]):
                    possible = False
                    break
            
            if possible:
                candid.add(userId)
        target.append(candid)

    dfs(target, 0, [], len(banned_id))
    
    return len(answer)

 

후기

 

중복을 없앨때는 문자열로 만들어서 제거해보자.

정렬과 join이 굉장히 유용하다.