[프로그래머스] 불량 사용자 - 카카오 19년 동계 인턴

 

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

프로그래머스

 

 

 

 

 

프로그래머스 랜덤 AI 추천 문제로 뜬 문제! 레벨 1문제인줄 알았지만, 풀고나니 레벨3 문제였네요.. 왠지 풀다가 턱걸리는 느낌..

 

 

풀이의 파트를 2개로 나누어 접근했습니다.

 

1. 밴 id가 될 수 있는 user를 찾기

2. 찾은 user들의 조합으로 겹치지 않는 조합구하기

 

 

1 의 경우 banned_id를 돌면서 user와 길이가 같고, *표시가 되어있지 않은 알파벳 위치가 동일한 user를 저장하는 방식으로 접근

 

2 의 경우 1의 결과로 나온 가능한 user의 조합을 DFS로 구하며 겹치는 조합을 set을 활용해 시간을 줄이는 방법을 사용했습니다.

 

입출력

 

 

def solution(user_id, banned_id):
    answer = []
    
    for ban in banned_id:
        tempdic = {}
        for idx, alpha in enumerate(ban):
            if alpha != '*':
                tempdic[idx] = alpha
                
        tempAnswer = []
        for user in user_id:
            flag = False
            # user와 ban_id의 길이가 다르다면 볼 필요도 없음
            if len(user) != len(ban):
                flag = True
                continue
            for key in tempdic.keys():
                if user[key] != tempdic[key]:
                    flag = True
                    break
            # tempAnswer에는 해당 ban_id에 속할 수 있는 user_id들을 저장
            if not flag:
                tempAnswer.append(user)
                  
        answer.append(tempAnswer)
    realAnswer = []
    
    def dfs(cur, idx):
        if len(cur) == len(answer):
            if set(cur) not in realAnswer:
                realAnswer.append(set(cur))
            return
        
        for i in range(len(answer[idx])):
            if answer[idx][i] not in cur:
                dfs(cur + [answer[idx][i]], idx+1)
    
    dfs([], 0)
    
    return len(realAnswer)