불량 사용자*

programmers.co.kr/learn/courses/30/lessons/64064

코딩테스트 연습 - 불량 사용자

 

해결 방법 : 모든 경우의 수 탐색

• user_id에 대해 banned_id 수로 조합을 만든다. (불량 사용자 리스트에 매칭될 수 있는 '중복 없는' 경우들)
• 위에서 만든 case들과 banned_id리스트가 일치 될 수 있는지 확인
  • 이 때, 그리디하게 순차적으로 접근하며 매칭을 단정지으면 안된다.
  • ex) case = ['aaa', 'bbb', 'aac'], banned_id = ['aa*', 'bb*', '*aa'] // 이 예시는 case가 불량 사용자들로 매칭되야 하는 경우인데 'aaa' → 'aa*' 를 확정 지으면 남은 두개의 id는 매칭이 불가능해진다.
  • 결국 case와 banned_id 또한 모든 경우를 탐색하도록 해야한다. → 순열 사용.  
  • id 간 비교는 is_equal() 

 

from itertools import combinations, permutations

def solution(user_id, banned_id):
    answer = 0
    cases = combinations(user_id, len(banned_id))
    
    for case in cases:
        check = False
        for c in permutations(case, len(case)):
            for i in range(len(case)):
                if is_equal(c[i], banned_id[i]) == False: break
                if i == len(case) - 1: check = True # 모든 id들이 불량 사용자와 일치
            
            if check: # 불량 사용자 조합으로 확인되면 answer++, 더 이상 비교 X
                answer += 1
                break
                    
    return answer

def is_equal(str1, str2): # id 일치 판별
    if len(str1) != len(str2): return False
    return len(['unequal' for s1, s2 in zip(str1, str2) if s1 != s2 and s2 != '*']) == 0

 

 

이전 풀이와 비교

: 접근 방식은 다르지만 모든 경우를 탐색한다는 점에서는 비슷하다.

하지만 이번 풀이는 조합을 사용하여 매칭 중복 검사를 할 필요가 없다.