[BOJ] 1097 - 마법의 문자열 (Python)

 

 

아이디어

 

크기가 N인 순열로 만들어진 새로운 문자열의 패턴이 K가 되는 순열의 수를 구한다.

 

 

풀이 #1

 

입력 받은 단어들을 리스트 S_list에 저장하고, 순열을 만드는 함수 perm을 호출한다.

 

함수 perm의 for문에서는 차례로 순열에 따라 S_list의 단어를 배치하고 재귀 호출한다.

순열의 배치를 마치면 join으로 새로운 문자열을 만들고, 딕셔너리 S_dict에 문자열을 키로 문자열의 수를 저장한다.

 

함수 perm이 종료된 후 S_dict에 저장된 문자열 S와 문자열 수 cnt를 차례로 꺼내

문자열의 길이를 문자열 패턴의 길이로 나눈 값이 K이면 결과값 res에 cnt를 더한다.

 

def perm(idx):
    if idx >= N:
        S = ''.join(S_list)
        if S in S_dict:
            S_dict[S] += 1
        else:
            S_dict[S] = 1
        return
    perm(idx+1)
    for i in range(idx+1, N):
        S_list[i], S_list[idx] = S_list[idx], S_list[i]
        perm(idx+1)
        S_list[i], S_list[idx] = S_list[idx], S_list[i]

N = int(input())
S_list = [input() for _ in range(N)]
S_dict = dict()
K = int(input())
perm(0)
res = 0
for S, cnt in S_dict.items():
    if len(S)//(S*2).find(S, 1) == K:
        res += cnt
print(res)

 

 

딕셔너리를 사용하지 않는 코드는 메모리가 더 적게 사용되지만 더 느렸다.

# 메모리가 더 적게 사용되나 더 느린 코드
def perm(idx):
    global res
    if idx >= N:
        S = ''.join(S_list)
        if len(S)//(S*2).find(S, 1) == K:
            res += 1
        return

 

 

 

풀이 #2

 

itertools의 permutations 함수를 이용해 간단하게 순열을 만들어낼 수도 있다.

 

import itertools

N = int(input())
S_dict = dict()
for P in itertools.permutations([input() for _ in range(N)], N):
    S = ''.join(P)
    if S in S_dict:
        S_dict[S] += 1
    else:
        S_dict[S] = 1
K = int(input())
res = 0
for S, cnt in S_dict.items():
    if len(S)//(S*2).find(S, 1) == K:
        res += cnt
print(res)