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

김지민·2022년 4월 26일

문제

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

코드

#불량사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외
# 이벤트 당첨자 아이디 중 일부 문자를 "*"문자로 가려서 전달
# 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디

#숫자로 세면 안되는 이유, 중복이 있을 수 있음
#(a,b,c,d) ,(a,b,d,c)
#모든 banned_id 값이 모든 user_id 값에 일대일 대응이 되는지

from itertools import combinations
from itertools import permutations
def solution(user_id, banned_id):
    answer = 0
    
    items = list(combinations(user_id,len(banned_id)))
    
    for item in items:
        able  = list(permutations(item,len(item)))
        for it in able:
            dictions = dict()
            for b in banned_id:
                for u in it:
                    flag = True

                    if u not in dictions.keys():
                        dictions[u] = 0

                    if dictions[u] != 0 or (len(u) != len(b)):
                        continue

                    for i in range(len(u)): #길이가 같다면
                        if b[i] == "*":
                            continue
                        elif u[i] != b[i]:
                            flag = False
                            break

                    if flag :
                        dictions[u] += 1
                        break
                        
            if sum(dictions.values()) == len(banned_id):
                answer += 1
                break
                    
    return answer

생각거리

일단 우리가 고려해야 할 사항이 많았다.

처음에 생각했지만 틀린 알고리즘과 그 이유

1. 사용자 아이디에 해당하는 불량 사용자 인원수를 count 해서 모든 count의 수 곱

사용자 아이디 (a,b,c)와 (a,c,b)는 하나의 경우의 수이다. 이전의 경우의 수까지 고려를 못하기 때문에, 이 경우 중복을 빼 줄 수 없다.

2. 후보 사용자 아이디 조합을 탐색하여 불량 아이디와 비교해서 길이가 같고, 모든 문자열이 같으면 dictionary의 불량 아이디 value 값을 증가시킨다.

불량 아이디는 중복이 발생하여 생길 수 있다. dictionary로 중복을 검사하는 것은 옳은 방법이 아니다.

3. 후보 사용자 아이디 조합을 탐색하여 불량 아이디와 비교해 길이가 같고, 모든 문자열이 같으면 dictionary의 사용자 아이디 value값을 증가시킨다.

사용자 아이디 (abdc,abcc) 불량자 아이디 (ab-- , abd- ) 인 경우 abdc인 경우는 ab-- , abd- 두가지 모든 경우에 만족하지만, abcc는 ab-- 만 만족한다. 하지만 for문을 돌면서 순차적으로 탐색할 때, ab-- 은 abdc에 일치되어 다시 탐색할 기회를 가질 수 없고, abcc는 어떠한 불량 아이디와도 만족할 수 없는 결과가 나타난다. 때문에 사용자 아이디의 다른 순열도 고려해야한다.
모든 사용자 아이디의 순열로 탐색한다면, 중복의 문제를 해결할 수 없으므로, 조합을 구한 다음, 조합을 다시 순열하여 한번이라도 만족하면 해당 조합의 탐색을 그만 두어야 한다.

실수

if elif를 설정할 때, if 문에 해당 하더라도, 다음 elif문을 확인 해야한다면, if, if문을 작성 해야한다.

다른 풀이

중복조합
불량 사용자의 인덱스에 해당 사용자 아이디를 append
append한 사용자 아이디를 중복 순열 함
중복순열한 결과의 set이 불량사용자의 길이와 answer set에 add

from itertools import product

list1 = [[1,1],[2,2],[3,3]]

print(list(product(*list1)))

# [(1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 2, 3)]

from itertools import product

list1 = [[1,2],[3,4],[5,6]]

print(list(product(*list1)))

# [(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]