문제 링크

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

풀이 방법

먼저 banned_id를 기준으로 user_id를 하나씩 돌면서

• 서로 글자수가 같고,
• *를 제외한 모든 글자가 서로 똑같은 user_id를 찾는다.

그걸 candidates 리스트로 넘겨준다. 그러면 각 banned_id가 가질 수 있는 후보 리스트가 완성이 된다.

이제 candidates의 각 리스트를 돌면서 dfs로 모든 경우의 수를 따져주면 된다.

dfs의 파라미터로

앞으로 탐색해야할 banned_id에 해당하는 user_id 리스트 candidates,

선택하지 않은 user_id 리스트 users,

이번 경우의 수가 담긴 result,

최종 결과가 들어갈 세트 results가 들어간다.

중간에 기존에 있던 레퍼런스들이 아닌 deepcopy를 이용해 기존 내용이 똑같이 담긴 새로운 리스트들이 생성되는데

그렇게 하지 않으면 재귀를 이용한 백트랙킹이 안되기 때문이다.

이해가 되지 않는다면 예를 들어보자.

입력값이 user_id: ["frodo", "fradi", "crodo", "abc123", "frodoc"], banned_id: ["*rodo", "*rodo", "******"]로 주어졌을 때 (입출력 예시2번)

candidates는 [['frodo', 'crodo'], ['frodo', 'crodo'], ['abc123', 'frodoc']] 로 나오게 된다.

['frodo', 'crodo'] 이 리스트가 2번 들어간 이유는 banned_id에 "*rodo" 이 조건이 2번 들어가있기 때문에 중복처리를 해주지 않고 들어가 있기 때문이다.

이제 dfs 함수로 들어가 ['frodo', 'crodo'] 이 아이템부터 경우의 수를 따져본다.

여기서 frodo를 선택한다면 다음 아이템에선 frodo 또는 crodo,

다음 아이템에선 abc123 또는 frodoc을 선택할 수 있다.

반대로 여기서 crodo를 선택한다면 똑같이 다음 아이템에선 frodo 또는 crodo,

다음 아이템에선 abc123 또는 frodoc을 선택할 수 있다.

결국 results값으로

['frodo', 'crodo', 'abc123']

['crodo', 'frodo', 'abc123']

['frodo', 'crodo', 'frodoc']

['frodo', 'crodo', 'frodoc']

이 4 가지 경우가 나올 수 있다.

하지만 문제 조건에 나와있듯이 원소의 순서에 상관없이 리스트에 담긴 원소가 같다면 동일한 경우로 생각하기 때문에

중복된 부분을 제거해주어야 한다.

세트를 통해서 중복을 없앨 수 있고 그러기 위해선 중복된 케이스가 같은 원소여야 한다.

하지만

['frodo', 'crodo', 'abc123']

['crodo', 'frodo', 'abc123']

이 케이스를 세트에 넣어준다면 다른 원소로 인식이 될 것이다. (애초에 리스트는 세트에 삽입하지 못 하지만..)

같은 원소로 인식하기 위해서 dfs의 base case로 해당 스택까지 트랙킹해온 result배열을 정렬해 준다.

그리고 리스트를 튜플에 넣는다면 hashable하지 않기 때문에 리스트를 튜플로 바꿔준다. (원소의 순서 고정)

1

['frodo', 'crodo', 'abc123'] => {'crodo', 'frodo', 'abc123'}로 변한됨

마지막으로 세트로 선언된 results에 넣어주면

['frodo', 'crodo', 'abc123']

['crodo', 'frodo', 'abc123']

와 같은 케이스는 중복처리 되어 하나만 남게된다.

최종적으로 results가 가지고 있는 각 경우의 집합?의 갯수를 세어주면 된다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import copy

def dfs(candidates, users, result, results):
  if not candidates:
    results.add(tuple(sorted(result)))
    return

  new_candidates = copy.deepcopy(candidates)
  curr = new_candidates.pop()
  for item in curr:
    if item in users:
      new_result = copy.deepcopy(result)
      new_result.append(item)
      new_users = copy.deepcopy(users)
      new_users.remove(item)

      dfs(new_candidates, new_users, new_result, results)


def solution(user_id, banned_id):
  candidates = []

  for bid in banned_id:
    temp = []
    for uid in user_id:
      found=True
      if len(bid) != len(uid):
        continue
      for i in range(len(bid)):
        if bid[i] == "*" or bid[i] == uid[i]:
            continue
        else:
            found=False
            break

      if found:
        temp.append(uid)

    candidates.append(temp)

  results = set()
  dfs(candidates, user_id, [], results)

  return len(results)

배운 점

파이썬의 함수 인자 전달 방식은 call-by-object-reference이다.

mutable한 타입은 call-by-value로,

immutable한 타입은 call-by-reference로 함수의 인자가 전달된다.

나는 다른 언어를 쓰던 습관이 남아있어 call-by-value인 줄 알고

dfs를 할 때 인자로 넘겨준 값이 예상한 값과 다른 값이 나왔다.

copy 모듈을 이용해 deepcopy를 해서 레퍼런스가 아닌 새로운 객체가 넘겨지도록 바꾸어주었다.

++ 이러한 방식이 백트랙킹 임을 깨닫게 되었다!!!

++ 세트에 리스트를 넣을때는 튜플로 변환해서 넣어줄 수 있다는 것을 알았다.

댓글 공유