[프로그래머스] 불량 사용자

 

📌문제

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

 

🎖️난이도

Level 3

 

✔️풀이

# 2019 카카오 개발자 겨울 인턴십

from itertools import product

def isPossible(user_id, banned_id):
    if len(user_id) != len(banned_id):
        return False
    for i in range(len(banned_id)):
        if banned_id[i] == '*':
            continue
        elif banned_id[i] != user_id[i]:
            return False
        
    return True

def solution(user_id, banned_id):
    
    can_banned = []
    for i in range(len(banned_id)):
        can_banned_tmp = []
        for j in range(len(user_id)):
            if isPossible(user_id[j], banned_id[i]):
                can_banned_tmp.append(user_id[j])
        can_banned.append(can_banned_tmp)
    
    # 오답 (test case 5번 시간초과)
    #product_list = set([''.join(sorted(list(item))) for item in list(map(set, list(product(*can_banned)))) if len(item) == len(banned_id)])
    
    # 정답
    product_set = set()
    for item in map(set, product(*can_banned)): # 중복 순열
        if len(item) == len(banned_id):
        	product_set.add(''.join(sorted(list(item)))) # 중복 제거
                                
    return len(product_set)

 

🧠노트

dfs 문제라는데 dfs로 풀이하는 법은 잘 모르겠고 

구현 + 중복순열(product)으로 풀었다.

 

그리고 이 문제의 관건은 test case 5번 이었는데,

시간초과를 막으려면 

banned_id에 있는 애들에 대해서 제제 아이디가 될 가능성이 있는 user_id를 구해놓은 리스트인 "can_banned"를 

2번 순회(for)하지 않아야 한다!

 

즉, 3번째 예제 case에 대해서 "can_banned"를 구하면 

이렇게 나오는데

얘를 이용해서 중복순열(product(*can_banned))을 구한 후 중복 경우의 수를 제거하기 위해

2번 순회하면 안된다! (주석처리 한 것처럼 해도 시간초과...)

 

또한, set 안에는 set나 list를 넣지 못하므로 (mutable, unhashable 하므로)

set를 list로 바꾸고 sort 해준 후 ''.join을 통해 문자열(string)로 바꿔서 set에 넣어준다!

그러면 중복 제거 가능!

# 핵심 코드
product_set = set()
for item in map(set, product(*can_banned)): # 중복 조합
    if len(item) == len(banned_id): 
    	product_set.add(''.join(sorted(list(item)))) # 중복 제거

 

🔍참고

[ product 응용 : 3개 이상의 데카르트 곱 ]

• product : 데카르트 곱(cartesian product), 곱집합
• 2개 이상의 리스트(or 집합) 끼리의 중복 순열을 구할 때 사용 (순서 O, 중복 O)
• 만약 product의 인자로 들어갈 대상의 개수를 미리 알고 있다면, 일일이 계속 넣어주면 되지만
• 만약 조합할 대상의 개수가 유동적이라면?
  • product( * list) !!! 

from itertools import product

# case 1) 중복순열할 대상들이 미리 주어져 있을 때
A = [1, 2, 3]
B = [4, 5, 6]
C = [7, 8, 9]
print(list(product(A, B, C)))

# case2) 중복순열할 대상들의 개수가 유동적일 때 (모를 때) => Asterisk(*) 이용
A = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(list(product(*A))) # A 내부의 1차원 리스트들끼리 중복순열

# case3) 하나의 대상으로 repeat횟수 주기
A = [1, 2, 3]
print(list(product(A, repeat=2))) # A 2개로 중복 순열 
# => [(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

 

cf. 참고 : Asterisk(*) 연산자를 이용한 Unpacking

[백준] 11403. 경로 찾기

 

 

[ set에 add 할 수 없는 것들 : unhashable type == mutable]

해시할 수 없는 타입(unhashable) == 변형이 가능한 타입(mutable)!

 

즉, set에 넣으려면 hash할 수 있는, 변형이 불가능한(immutable) 자료형만 가능하다!!

 

- 변형이 불가능한 자료형(immutable) : number(int, float..), tuple, string => set에 add 가능!
- 변경이 가능한 자료형(mutable) : list, dict, ndarray => set에 add 불가능!

 

cf. 참고 : immutable vs mutable

[Python] 얕은 복사🥵 vs 깊은 복사🤗