# ---------- Import ----------
from sys import stdin
input = stdin.readline
# ---------- Function ----------
def mulMatrix(A: list, B: list) -> list:
N = 2
result = [[0]*N for _ in range(N)]
for m in range(N):
for n in range(N):
for k in range(N):
result[m][n] += A[m][k] * B[k][n]
result[m][n] %= MOD
return result
def power(base, exponent):
if exponent == 1:
return base
tmp = power(base, exponent // 2)
if exponent % 2:
return mulMatrix(mulMatrix(tmp, tmp), base)
else:
return mulMatrix(tmp, tmp)
def fibonacci(N):
result = power([[1, 1], [1, 0]], N)
return mulMatrix(result, [[1, 0],[0, 0]])[1][0] % MOD
# ---------- Main ----------
small, big = map(int, input().split())
MOD = 1_000_000_000
big = fibonacci(big+2)
small = fibonacci(small+1)
print((big - small) % MOD)
# ---------- Comment ----------
# big = fibonacci(big+2) - 1
# small = fibonacci(small+1) - 1
# big - small = fibonacci(big+2) - 1 - (fibonacci(small+1) - 1)
# = fibonacci(big+2) - fibonacci(small+1)
# so can skip intercept
# ---------- Import ----------
from collections import deque
import sys
input = sys.stdin.readline
# ---------- Function ----------
def is_Bipartite(graph, node_count):
visited = [-1] * (node_count+1)
for node in range(node_count+1):
# group1 number is 1, group2 number is 0
if visited[node] != -1:
continue
group = 1
visited[node] = group
Q = deque([(node, group)]) # node, group
while Q:
node, group = Q.popleft()
for i in graph[node]:
if visited[i] == group:
return "NO"
if visited[i] == -1:
visited[i] = (group+1) % 2
Q.append((i, (group+1) % 2))
return "YES"
# ---------- Main ----------
for _ in range(int(input())):
node, edge = map(int, input().split())
graph = [[] for _ in range(node+1)]
for _ in range(edge):
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s)
answer = is_Bipartite(graph, node)
print(answer)
# ---------- Import ----------
from collections import defaultdict
import sys
input = sys.stdin.readline
# STOP, RGT, LFT, UP, DN
dr = [(0, 0), (0, 1), (0, -1), (-1, 0), (1, 0)]
# ---------- Function ----------
def OUT_OF_BOUND(x, y):
if 0 <= x < size and 0 <= y < size: return False
else: return True
def Action_by_Color(color, x, y, nx, ny):
if color == 0: step = 1
else: step = -1
cur_loc_chess = loc_2_cur[(x, y)] # current location chess info
for c in cur_loc_chess: num_2_loc[c] = (nx, ny) # all chess move
loc_2_cur[(nx, ny)] = loc_2_cur[(nx, ny)] + cur_loc_chess[::step] # stack
loc_2_cur[(x, y)] = [] # current location is empty
return len(loc_2_cur[(nx, ny)]) # how many chess stack
def MyTurn():
for chess in range(1, piece_count + 1):
loc = num_2_loc[chess]
dir = num_2_dir[chess]
cur = loc_2_cur[loc]
idx = cur.index(chess)
# Not bottom-most
if idx: continue
x, y = loc
dx, dy = dir
nx, ny = dx + x, dy + y
# Checking chess-board color
if OUT_OF_BOUND(nx, ny): state = 2
else: state = chess_board[nx][ny]
# Color is blue or out of bound
if state == 2:
rx, ry = -dx + x, -dy + y
num_2_dir[chess] = (-dx, -dy)
# Checking chess-board color
if OUT_OF_BOUND(rx, ry): state = 2
else: state = chess_board[rx][ry]
# Reverse is blue, then nothing action
if not (state == 2):
stack = Action_by_Color(state, x, y, rx, ry)
if stack >= 4: return "END"
# Color is white or red
else:
stack = Action_by_Color(state, x, y, nx, ny)
if stack >= 4: return "END"
return "CONTINUE"
# ---------- Main ----------
size, piece_count = map(int, input().split())
chess_board = [list(map(int, input().split())) for _ in range(size)]
# declaration
num_2_loc = dict()
num_2_dir = dict()
loc_2_cur = defaultdict(list)
# init
for i in range(piece_count):
row, col, direction = map(int, input().split())
num_2_loc[i+1] = (row-1, col-1)
num_2_dir[i+1] = dr[direction]
loc_2_cur[(row-1, col-1)].append(i+1)
# game set condition: turn ＜ 1000
for turn in range(1, 1000 + 1):
state = MyTurn()
if state == "END":
print(turn)
break
# more than or equal to 1000
else:
print(-1)
가뜩이나 느린 Python은 당연히 빠른 입력을 위해 stdin.readline을 사용한다.
그리고 추후에 방향으로 사용할 dr 리스트를 미리 선언해주었다.
0번 index에 (0, 0)을 넣은 이유는, 오른쪽 방향이 1부터 시작하기 때문에 padding한 것이다.
# ---------- Main ----------
# init
for i in range(piece_count):
row, col, direction = map(int, input().split())
num_2_loc[i+1] = (row-1, col-1)
num_2_dir[i+1] = dr[direction]
loc_2_cur[(row-1, col-1)].append(i+1)
체스말만큼 체스말 정보를 받아온다.
이때 row와 col은 index가 0부터 시작하는 것을 염두하여 1을 뺀 뒤, dict()에 위치를 저장했다.
방향은 바로 위에서 말한 dr 리스트를 이용하여 dict()에 저장한다.
각 판의 위치 정보는 나중에 여러 개의 말이 쌓이기 때문에 list로 초기화했고, append로 추가한다.
모든 코드에서 체스말 번호는 1부터 시작하는 게 편하다고 판단하여, i+1로 지정해주었다.
또한, 변수명은 최대한 직관적으로 지어보았다.
체스말 번호를 입력하면 위치가 나오는 딕셔너리(num_2_loc)처럼 말이다.
dict()를 초기화할 때 2가지를 생각해주었다.
사실 둘 다 크게 의미는 없지만, 혹시 모를 상황을 대비하여 염두하긴 했다.
1. 순서대로 입력을 받는가 2., 순서대로 접근이 가능한가
dict() 자료형의 경우, 순서를 보장하지 않아 key-value 쌍 순서가 마구잡이가 되는 경우가 종종 있다.
하지만 초기화할 때 숫자가 key인 경우, 입력 받은 순서는 지켜지기에 문제 없다고 생각했다.
왜냐하면 문제에서 체스말 번호 순서대로 입력이 주어지기 때문이다.
하지만 list와 달리 1번과 2번 모두 key-value로 찾기 때문에 크게 문제될 사항은 아니다.
어디까지나 추후에 순차 접근이 필요할 수도 있을 것 같아 고려한 상황이다.
# ---------- Main ----------
# game set condition: turn ＜ 1000
for turn in range(1, 1000 + 1):
state = MyTurn()
if state == "END":
print(turn)
break
# more than or equal to 1000
else:
print(-1)
처음에 문제를 읽으면서, '4개가 쌓이지 않는 경우도 있지 않을까?'라는 생각을 했다.
그랬더니 아니나 다를까, 출력 조건에 "절대로 게임이 종료되지 않는 경우에는 -1을 출력한다"가 있었다.
그리고 그 앞부분에는 "값이 1,000보다 크거나"가 있었다.
절대로 게임이 끝나지 않는다는 것은 반복을 1000회 이상 한다는 말과 같다.
딱 1000번 돌렸을 때, 결과가 나오지 않는다면? 무조건 -1을 출력하면 된다는 말이다.
이를 Python3의 for-else문을 활용하여 구현했다.
만약 1턴씩 진행하면서 종료한다면, 몇 번째 turn인지 출력하고 종료한다.
이때 break로 빠져나간다면 else문으로 빠지지 않는다.
for-else에서 else는 break로 빠져나가지 않고 전부 순회했을 때에만 실행하기 대문이다.
# ---------- Function ----------
def MyTurn():
for chess in range(1, piece_count + 1):
loc = num_2_loc[chess]
dir = num_2_dir[chess]
cur = loc_2_cur[loc]
idx = cur.index(chess)
# Not bottom-most
if idx: continue
x, y = loc
dx, dy = dir
nx, ny = dx + x, dy + y
1턴씩 진행하는 함수를 구현할 차례이다. 의사 코드(pesudo code)는 생각보다 간단하다.
1번부터 piece_count번까지 움직일 수 있는지 확인한다.
움직일 수 있다면, 이동하려는 칸 색상에 따라 적절히 움직인다. 이게 전부다.
Main에서 dict()에 초기화를 제대로 했다면, 위에서 불러오는 건 쉽다.
loc, dir, cur, idx로 현재 체스말에 대한 정보를 가져온다.
이때 idx가 0인 경우에만 행동을 진행한다. 왜? 가장 아래에 있어야만 움직이기 때문이다.
따라서 0이 아닌 True 값이라면 continue로 넘어간다.
그후 체스말을 움직여야 한다면, 정보를 조금 더 잘게 쪼갠다.
loc를 현재 x, y로 두고, dir를 이동 방향 dx, dy로 두고, nx, ny를 구한다.
# ---------- Function ----------
def OUT_OF_BOUND(x, y):
if 0 <= x < size and 0 <= y < size: return False
else: return True
체스판 위에서 움직이기 위해, nx, ny를 계산했다.
그렇다면 당연히 범위 밖으로 벗어가는 경우도 존재한다.
o <= x < size ~~~~~라고 장황하게 적지 말고, 함수로 빼주자.
함수 존재 의의 중 하나가 중복 최소화이지 않은가.
함수 이름은 OUT_OF_BOUND, 즉 범위를 벗어났는가? 라는 말이다.
그럼 결과도 이에 맞춰서 주는 게 편하다.
범위를 벗어난다면 True를, 벗어나지 않는다면 False를 반환하자.
# ---------- Function ----------
def MyTurn():
''' (중략) '''
# Checking chess-board color
if OUT_OF_BOUND(nx, ny): state = 2
else: state = chess_board[nx][ny]
# Color is blue or out of bound
if state == 2:
''' do something '''
# Color is white or red
else:
stack = Action_by_Color(state, x, y, nx, ny)
if stack >= 4: return "END"
return "CONTINUE"
이제 진짜 이동하는 본격적인 코드를 작성해보자.
체스말이 이동할 nx, ny가 범위를 벗어났는지부터 확인하자. 벗어났다면 청색(2)가 같은 판정이다.
아니라면 chess_board의 색상을 가져오면 된다.
만약 청색이라면 어떤 행동을 하는지는 잠시 뒤에 살펴보고,
백색이라면 말을 그대로 쌓아올리고, 적색이라면 말을 뒤집어서 쌓아올린다.
어라? 쌓아올리는 순서만 다를 뿐 나머지는 전부 같다? 이것 또한 함수로 뺄 수 있다.
Action_by_Color()라는 함수를 만들어, 현재 위치(x, y)와 이동할 위치(nx, ny), 색상(state)를 넘겨주자.
Action_by_Color() 함수 return은 이동할 위치(nx, ny)의 말 개수다.
얼마나 쌓여있는지(stack) 개수를 가져와서, 4 이상이라면 그대로 "END"를 뱉고 종료한다.
1턴을 돌면서 "END"가 한 번도 나오지 않는다면 마지막에 "CONTINUE"를 뱉고 종료한다.
# ---------- Function ----------
def Action_by_Color(color, x, y, nx, ny):
if color == 0: step = 1
else: step = -1
cur_loc_chess = loc_2_cur[(x, y)] # current location chess info
for c in cur_loc_chess: num_2_loc[c] = (nx, ny) # all chess move
loc_2_cur[(nx, ny)] = loc_2_cur[(nx, ny)] + cur_loc_chess[::step] # stack
loc_2_cur[(x, y)] = [] # current location is empty
return len(loc_2_cur[(nx, ny)]) # how many chess stack
Action_by_Color() 함수를 살펴보자.
우선 현재 위치에 있는 말들을 cur_loc_chess에 저장한다.
cur_loc_chess를 하나씩 돌면서(c), 다음 위치(nx, ny)로 바꿔준다.
그리고 다음 위치(nx, ny)의 체스말 뒤에 쌓아주면 된다.
이때 백색은 정방향, 적색은 역방향이기에, 처음에 if-else로 step를 정해주어서 사용한다.
다음 위치(nx, ny)에 옮겨주었으니, 현재 위치(x, y)는 텅 빈 상태로 만든다.
마지막으로 다음 위치(nx, ny)에 쌓인 말 개수를 return한다.
처음에 저장할 때, 각 말들의 현재 위치, 이동 방향 등을 dict()로 따로 저장했다.
정보를 가져올 때는 편하지만, 관리하기에는 살짝 헷갈릴 수 있으니 놓치지 않도록 하나씩 잘 생각하자.
# ---------- Function: do something ----------
rx, ry = -dx + x, -dy + y
num_2_dir[chess] = (-dx, -dy)
# Checking chess-board color
if OUT_OF_BOUND(rx, ry): state = 2
else: state = chess_board[rx][ry]
# Reverse is blue, then nothing action
if not (state == 2):
stack = Action_by_Color(state, x, y, rx, ry)
if stack >= 4: return "END"
대망의 마지막 부분, chess_board의 색상이 blue일 때 상황이다.
청색이라면 이동 방향이 반대다. 따라서 reverse_x, y라는 의미로 rx, ry를 새롭게 계산한다.
그리고 현재 체스말(chess)의 방향을 바꿔서 저장하는 것을 잊지 말자.
반대 방향(rx, ry)에 대해서도 OUT_OF_BOUND()를 확인해야 한다.
이때 반대 방향(rx, ry)의 색상(state)이 청색인 경우는 고려하지 않아도 된다.
청색 반대가 청색인 경우에는 아무 것도 하지 않기 때문이다. 문제가 그렇다.
즉, 청색이 아닌 경우(not (state == 2))만 고려하면 된다.
이때 코드는? 처음에 색상을 판단했을 때의 코드를 그대로 가져오면 된다.
단 nx, ny가 아니라 rx, ry로 바꾸는 것을 까먹지 말자.
만약 Action_by_Color() 함수로 빼지 않았다면 코드가 무지막지하게 길어졌을 것이다.
X_FFT = FFT(X, 1) # FFT
Y_FFT = FFT(Y, 1) # FFT
mul = [X_FFT[l] * Y_FFT[l] for l in range(N)]
inverse = FFT(mul, -1) # IFFT
X와 Y를 각각 FFT 연산을 하여 저장한다.
그리고 두 요소를 각각 곱해서 mul이라는 리스트에 따로 저장해준다.
mul 리스트를 IFFT(역 연산)를 수행하면, 원하는 결괏값들이 나온다!
print(max(round(real_num.real / N) for real_num in inverse))
역 연산을 수행해서 나온 inverse 리스트는 현재 복소수가 들어가 있다.
이렇게 정규화하는 이유는 FFT 과정 중에 각 요소가 N만큼 곱해졌기 때문이다.
이를 전체 길이N으로 나누어 정규화해야 한다.
또한, 여기서 원하는 값은 정수다. 즉 변환을 해줘야 한다.
real 메소드를 사용하면, a + bi의 복소수 형태에서 실수만을 취해준다.
복소수만큼 손실이 발생했기 때문에, round() 함수로 반올림 해준다.
그리고? 이들 중 최댓값(max)를 구하면 된다.
def FFT(a: list, inverse: int) -> list:
N = len(a)
if N == 1: return a
even = FFT(a[0::2], inverse)
odd = FFT(a[1::2], inverse)
w_N = [exp(inverse*2j*pi*n/N) for n in range(N//2)]
frt = [even[i] + w_N[i] * odd[i] for i in range(N//2)]
bck = [even[i] - w_N[i] * odd[i] for i in range(N//2)]
return frt + bck
대망의 FFT 알고리즘이다.
수학자 두 명이 고안해낸 '쿨리-튜키 알고리즘(Cooley-Tukey algorithm)'을 따라간다.
더 넓은 범위, 더 빠른 속도를 원한다면 'NTT(Number Theoretic Transform)'라는 알고리즘을 사용하기도 한다.
정수론의 소수(MOD)와 원시근을 이용한 방법이다. 하지만 여기서는 사용하지 않는다.
쉽게 말하면 DFT(이산 푸리에 변환)에서 중복으로 발생하는 연산이 있다.
중복은 주어진 전체 길이를 반으로 쪼갰을 때를 기준으로 존재한다.
따라서 반으로 나눠서 다시 푸리에 변환을 진행하는 방식으로 수행한다.
def FFT(a: list, inverse: int) -> list:
리스트 a와 정수 inverse를 입력받는다.
a는 FFT할 리스트이고, 정변환인지 역변환인지 나타내는 inverse 변수다.
놀랍게도 FFT와 IFFT는 단 하나의 값만 다르다!
따라서 코드를 아주 손쉽게 재사용할 수 있다.
N = len(a)
if N == 1: return a
리스트 a의 길이는 추후에도 사용하기에 N에 저장해준다.
N이 1이라면 더 이상 쪼갤 수 없다. 이때는 a를 그대로 반환하면 된다.
even = FFT(a[0::2], inverse)
odd = FFT(a[1::2], inverse)
위에서 푸리에 변환을 나눈다고 언급했다.
기함수와 우함수의 특징을 이용하여, 홀수 번째와 짝수 번째 index를 기준으로 나눈다.
(기함수는, 다른 말로 홀함수이다. y(-x) = -y(x)가 성립하는 특징을 갖는다.)
(우함수는, 다른 말로 짝함수이다. y(x) = y(-x)가 성립하는 특징을 갖는다.)
나눈 리스트는 FFT로 재귀를 돌려준다.
w_N = [exp(inverse*2j*pi*n/N) for n in range(N//2)]
나중에 곱해주기 위해서 가중치를 미리 리스트로 만들어둔다.
푸리에 변환에 의해 가중치 e^2𝝿jn을 곱해주어야 한다.
(이 가중치는 복소평면상에서 단위원 위의 점과 같다. 오일러 공식 eiθ =cosθ+isinθ을 응용한다.)
(파이썬에서는 복소수를 j로 사용한다.)
중복 값을 나눠서 계산하기에, 범위는 N // 2까지만 계산하면 된다.
위에서 언급한 FFT와 IFFT가 다른 단 하나의 부분이 이 코드다.
실제로 FFT는 2𝝿jn을 가중치로 사용하지만, IFFT는 -2𝝿jn을 가중치로 사용한다.
(역연산을 취하려면 fourier matrix를 뒤집어야 한다. 이때 -1이라는 값이 등장한다.)
따라서 처음 FFT 함수를 호출할 때, inverse에 1 혹은 -1을 입력받아서 맨 앞에 부호로써 곱해준다.
frt = [even[i] + w_N[i] * odd[i] for i in range(N//2)]
bck = [even[i] - w_N[i] * odd[i] for i in range(N//2)]
return frt + bck
두 가지 리스트를 합쳐서 반환하면 끝난다.
본래는 전체 길이(N)만큼 0으로 초기화 한 다음에, index에 맞게 값을 넣어주어야 한다.
하지만 파이썬의 리스트는 + 연산자를 지원해서, 앞뒤의 리스트를 구한 뒤 더해주면 된다.
FFT의 연산 결과(원리)에 의해서 위와 같은 과정을 따라간다.
from cmath import exp, pi
import sys
input = sys.stdin.readline
def FFT(a: list, inverse: int) -> list:
N = len(a)
if N == 1: return a
even = FFT(a[0::2], inverse)
odd = FFT(a[1::2], inverse)
w_N = [exp(inverse*2j*pi*n/N) for n in range(N//2)]
frt = [even[i] + w_N[i] * odd[i] for i in range(N//2)]
bck = [even[i] - w_N[i] * odd[i] for i in range(N//2)]
return frt + bck
length = int(input())
N = 1 << length.bit_length() + 1
A = list(map(int, input().split())) * 2 + [0] * (N - length * 2)
B = list(map(int, input().split()))[::-1] + [0] * (N - length)
A_FFT = FFT(A, 1) # FFT
B_FFT = FFT(B, 1) # FFT
mul = [A_FFT[l] * B_FFT[l] for l in range(N)]
inverse = FFT(mul, -1) # IFFT
print(max(round(real_num.real / N) for real_num in inverse))
결과적으로 FFT와 IFFT를 구분하지 않고 하나의 함수로 묶을 수 있었다.
또한, 처음에 받는 리스트의 길이가 2의 제곱수이든 아니든 상관하지 않고 동작할 수 있다.
# ---------- Import ----------
import sys
input = sys.stdin.readline
# ---------- Function ----------
def bit_check(num):
bit = []
while num & -num:
bit.append(num & -num)
num &= (num-1)
return bit
# ---------- Main ----------
N = int(input())
mp, mf, ms, mv = map(int, input().split())
foods = {2 ** i : tuple(map(int, input().split())) for i in range(N)}
possible_list = list()
for i in range(1, 2 ** N):
p, f, s, v = 0, 0, 0, 0
price = 0
is_possible = bit_check(i)
for bit in is_possible:
food_p, food_f, food_s, food_v, food_price = foods[bit]
p += food_p
f += food_f
s += food_s
v += food_v
price += food_price
if mp <= p and mf <= f and ms <= s and mv <= v:
possible_list.append((is_possible, price))
if not possible_list:
print(-1)
else:
possible_list.sort(key = lambda x: (x[1], x))
print(possible_list[0][1])
print(*list(map(lambda x: len(bin(x))-2, possible_list[0][0])))
# ---------- Import ----------
from copy import deepcopy
import sys
input = sys.stdin.readline
# ---------- Function ----------
def Rotate_90_Degree(board):
ret = [[0]*length for _ in range(length)]
for r in range(length):
for c in range(length):
ret[c][length-1-r] = board[r][c]
return ret
def Rotate_270_Degree(board):
ret = [[0]*length for _ in range(length)]
for r in range(length):
for c in range(length):
ret[length-1-c][r] = board[r][c]
return ret
def Reflect(board):
for i in range(length):
board[i] = board[i][::-1]
return board
def LFT(board):
for i in range(length):
line = list(filter(None, board[i]))
for idx in range(len(line)-1):
if not (line[idx] - line[idx+1]):
line[idx] *= 2
line[idx+1] = 0
line = list(filter(None, line))
line += [0] * (length - len(line))
board[i] = line
return board
def UP(board):
board = Rotate_270_Degree(board)
board = LFT(board)
return Rotate_90_Degree(board)
def DN(board):
board = Rotate_90_Degree(board)
board = LFT(board)
return Rotate_270_Degree(board)
def RGT(board):
board = Reflect(board)
board = LFT(board)
return Reflect(board)
def BoardGame2048(board, move_count):
if move_count == 5:
global max_block
max_block = max(max_block, max(map(max, board)))
return
for direct in ["U", "D", "L", "R"]:
copy_board = deepcopy(board)
BoardGame2048(switch[direct](copy_board), move_count+1)
return
# ---------- Main ----------
max_block = 0
switch = {"U":UP, "D":DN, "L":LFT, "R":RGT}
length = int(input())
board = [list(map(int, input().split())) for _ in range(length)]
BoardGame2048(board, 0)
print(max_block)
from itertools import permutations
import re
def regex_pattern(input_string):
return re.compile(input_string.replace("*", ".{1}"))
def solution(user_id, banned_id):
answer = []
count = 0
banned_id = list(map(regex_pattern, banned_id))
for case in permutations(user_id, len(banned_id)):
for c, b in zip(case, banned_id):
if not b.fullmatch(c):
break
else:
answer.append(tuple(sorted(case)))
return len(set(answer))
이때 user_id가 [frodo, crodo]이고, banned_id가 [*rodo, *rodo]라고 해보자.
*rodo는 각각 frodo, crodo가 될 수 있는 경우 2개가 있다. 그럼 2 * 2 = 4일까?
아니다. 이 점을 주의해야 한다. 중복하는 경우는 전부 하나로 취급한다.
import re
def regex_pattern(input_string):
return re.compile(input_string.replace("*", ".{1}"))
우선 '정규 표현식(Regular Expression)'을 활용하기로 했다.
*이 하나의 문자에만 대응하니 .{1}로 바꿔서 re.compile하여 사용하는 함수를 작성했다.
banned_id = list(map(regex_pattern, banned_id))
내장 함수 map을 활용하여 banned_id로 입력받은 모든 아이디를 컴파일해준다.
map 객체는 len() 같은 다른 built-in function을 사용하는 것이 불가능하기 때문에 list()로 변환한다.
번거롭게 반복문을 사용하지 않고, map() 함수와 함수를 변수처럼 사용하는 기능을 이용하였다.
from itertools import permutations
[ 제한사항 ]
ㆍ user_id 배열의 크기는 1 이상 8 이하입니다.
ㆍ banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
문제에 위와 같은 제한 사항이 존재했다.
어라? 생각보다 제한사항이 크지가 않았다.
그럼 banned_id에 대응하는 문자열을 찾아낸 다음에 경우의 수를 조합하는 방식이 아니라,
banned_id의 길이만큼 user_id를 조합하여 모든 경우의 수를 찾으면 되는 거 아닐까?
최악의 경우를 생각해보자.
user_id가 8이면서 banned_id도 8인 경우다. 8P8로 8!에 해당하는 숫자다.
8! = 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 40320개뿐이다.
따라서 브루트 포스로 모든 경우의 수를 확인해도 충분하다고 판단했다.
for case in permutations(user_id, len(banned_id)):
for c, b in zip(case, banned_id):
if not b.fullmatch(c):
break
else:
answer.append(tuple(sorted(case)))
위에서 생각한 것처럼 user_id를 banned_id의 길이만큼 경우의 수를 만든다.
이떄 combinations이 아니라 permutation을 활용한 것은 순서가 필요하기 때문이다.
정답에서 [frodo, crodo]와 [crodo, frodo]는 같은 것으로 취급하는데 모순처럼 보인다.
하지만 user_id가 [frodo, abc123]이라고 가정해보자.
그리고 banned_id가 [abc***, *rodo]라고 가정해보자.
user_id를 combinations을 해버리면 입력받은 순서를 유지한 채로 [frodo, abc123]만 존재한다.
하지만 분명하게 user_id와 banned_id는 하나하나 대응할 수 있는 상태다.
즉 이런 상황을 방지하기 위해서, 중복이 존재하더라도 우선은 permutation으로 확인해주었다.
어차피 중복은 나중에 제거하면 된다.
zip을 사용하여 permutations으로 나온 각각의 경우(case)를 묶어서 비교한다.
re.compile로 나온 b와 전부 일치하는지(fullmatch) 확인한다.
하나라도 일치하지 않는 경우가 있다면 해당 case는 무시해야 하는 경우다.
따라서 break로 빠져나온다.
만약 모든 경우에 대해서 break로 빠져나오지 않았다면, for - else 구문에서 else로 넘어간다.
나중에 중복을 제거해줘야 하기 때문에 정렬한 상태로 answer에 추가한다.
이때 주의해야 할 점은 저장한 후 자료 구조를 그대로 두면 안 된다는 것이다.
파이썬은 sort() 혹은 sorted() 내장 함수를 사용하면 list로 반환한다.
하지만 set 자료 구조를 사용할 때는 list는 사용할 수 없다. ( TypeError: unhashable type: 'list' )
set 또한 dict처럼 해시를 이용하기 때문에 키 값이 바뀌어서는 안 된다.
즉 키로 사용하는 값이 immutable 해야 한다는 뜻이다.
따라서 mutable한 list가 아닌 immutable한 tuple로 바꿔준 다음 추가한다.
return len(set(answer))
위에서 언급한 중복을 없애야 한다.
set() 자료 구조를 이용하여 간단하게 중복을 제거할 수 있다.
정렬한 상태로 answer에 담아주었기 때문에, 모든 경우의 수를 빠짐없이 중복을 제거할 수 있다.
