문제

Say that we have strings $s=s_1 s_2... s_m$ and $t=t_1t_2...t_n$ with $m < n$. Consider the substring $t'=t[1 : m]$. We have two cases:
1. If $s=t'$, then we set $s < _{Lex}t'$ because $s$ is shorter than $t$(e.g., APPLE < APPLET).
2. Otherwise, $s\neq t'$. We define $s < _{Lex}t$ if $s < _{Lex}t'$ and define $s > _{Lex}t$ if s > _{Lex}t'(e.g., APPLET < $_{Lex}ARTS because APPL < $_{Lex}$ARTS).

Given
A permutation of a most 12 symbols defining an ordered alphabet 𝒜 and a positive integer n(n$\leq$4).

Return

All strings of length at most $n$ formed from 𝒜, ordered lexicographically.

문제 해설

문제만 봐서는 약간 이해가 안갈 수 있다. 하지만 sample 데이터와 output을 보면 이해하기가 쉽다.

Sample Dataset

D N A
3

Sample Output

D
DD
DDD
DDN
DDA
DN
DND
DNN
DNA
DA
DAD
DAN
DAA
N
ND
NDD
NDN
NDA
NN
NND
NNN
NNA
NA
NAD
NAN
NAA
A
AD
ADD
ADN
ADA
AN
AND
ANN
ANA
AA
AAD
AAN
AAA

명백히 D N A 는 알파벳 순으로 나열되어 있지않다. output을 보면 주어진 데이터를 정해진 순서로 보고, 이 순서대로 1 ~ 3개의 글자열을 순서대로 나열하여 출력하라는 의미이다. Enumeration이 아니라 print가 전제인 문제이기 때문에 시간은 그렇게 생각하지 않아도 되는 문제라는 것을 어렴풋이 알 수 있다.

문제는 간단하게 해결할 수 있다. 재귀적으로 트리를 만들어가며 순서대로 출력을 하면된다. 먼저 D를 출력하고, D, N, A를 출력하고 DD를 출력했다면 다시 D, N, A를 출력해서, DDD, DDN, DDA를 출력하는 방식으로 재귀적으로 DNA를 n번 깊이까지 순회한다면 간단하게 문제를 풀 수 있다.

아래는 python 코드 이다.

alphas = 'D N A'
N = 3

alpha_ls = alphas.split(' ')

file = open("LEXV.txt", "w", encoding="UTF-8")

def print_alpha(alphas, cur, n):
	# 현재까지 쌓여온 string을 출력한다.
    file.write(cur + "\n")
	
    # n 번째 깊이에서 중단
    if n == N:
        return
    
    for a in alphas: # D, N, A를 순회
    	# 순회할 때, cur 에 다음 순회할 Alphabet을 추가.
        # Depth를 추가
        print_alpha(alphas, cur + a, n + 1)


print_alpha(alpha_ls, '', 0)
file.close()

처음에 bfs 써야 하나 했는데, 그냥 전체 순회이고, bfs는 그래프가 주어졌을 때 유용하게 사용할 수 있는 방법이라, 단순 재귀를 이용한 순회만으로 충분히 풀수 있었던 문제였다.