불량 사용자

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

프로그래머스

문제 요약:

아이디리스트와 벤된아이디리스트가 주어진다. 이때 벤된 아이디리스트는 중간중간에 *로 가려져있는데 어떤 문자든 가능하다. 아이디 리스트중 벤된 아이디들의 리스트를 구하여라. 단 순서는 상관없이 이름들이 같다면 같은것으로 친다.

 

소요시간:

40분

난이도3

 

코딩:

import re
import copy
def solution(user_id, banned_id):
	temp = [[] for _ in range(len(banned_id))]
	for i,ban in enumerate(banned_id):
		for user in user_id:
			#주어진ban_id 에서 *을 . 으로 바꾸어 무엇이 들어가도 해당되게 만든다. 
			if (key:= re.findall(ban.replace('*','.'),user)) != [] and len(ban) == len(user):
				#조건에 맞는 애들만 temp에 넣기
				temp[i].append(key[0])
	ans = set()
	
	def dfs(s,t):
		#끝까지 다 돌았을 때
		if t == len(temp) :
			#중복되는것이 없다면
			if len(s) == len(temp):
				#후보에 추가
				ans.add(''.join(sorted(list(s))))
		#끝까지 안돌았다면 확인
		else:
			for i in temp[t]:
				temp_set = s.copy()
				temp_set.add(i)
				dfs(temp_set,t+1)
	dfs(set(),0)
	
	return len(ans)

사실 re.find함수를 통해 조건에 해당하는 아이디를 찾는것은 10분도 되지않아 구현했지만, 그들의 조합을 구하는 로직을 짜는데 많은 시간을 소모했다, 결국 dfs 로 구현했는데, 위 코딩과 같이 temp를 돌며 하나씩 선택해주고 끝까지돌았을때 겹치는게 없다면 후보군에 넣어주었다 이때, 역시 후보군 중에서도 겹치는게 있을수 있기 때문에, (가령 두개의 banned리스트가 겹치는 두개의 아이디를 찾았다면 둘은 같은경우) 순서대로 정렬하여 합쳐준뒤 set함수에 넣어 중복을 가려냈습니다.

 

다른사람코드:

result = list(product(*result))
    for r in result:
        if len(set(r)) == len(banned_id):
            answer.add("".join(sorted(set(r))))

    return len(answer)

이 전까지의 로직은 똑같기 때문에 생략했고 result 리스트가 제 코딩에서 temp에 해당됩니다.

물론 DFS를통하여 중간에 겹치는게 발생했을때 바로바로 return을통해 나온다면 시간복잡도를 더 줄일 수 있겠으나, 

다음과같이 product함수를 이용하는것도 깔끔하기 때문에 가져왔습니다.

ex ) [['frodo', 'fradi'], ['frodo', 'crodo'], ['abc123', 'frodoc'], ['abc123', 'frodoc']] 

다음과 같이 result함수가 있을 때 앞에 *를 붙여주게되면 리스트의 차원이 풀어져서 

['frodo', 'fradi'], ['frodo', 'crodo'], ['abc123', 'frodoc'], ['abc123', 'frodoc'] 다음과 같이 되고, 이를 product함수에 넣으면 각각리스트에서 하나씩 골라주기 때문에 이 후부터는 제 코딩과 과정이 같습니다.