난이도

Gold 5

풀이 참고 유무

x

막힌 부분

x

문제

문제 바로가기
바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

예제 입력

4 6
a t c i s w

예제 출력

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

문제 검토

알파벳을 결정하는 것에 대한 조건들이 있고 그에 맞는 조건들로 알파벳을 선택한 뒤 회수하면서 백트랙킹을 수행하는 문제이다.

풀이(python)

Python

from sys import stdin
input=stdin.readline
l,c = map(int,input().split())
alpha=list(input().strip().split())
alpha=sorted(alpha)
for x in range(c):
    alpha[x]=[alpha[x],x]
visited=[False for _ in range(c)]
mo,za=0,0
s=''
#모음 집합
mos=set(['a','e','i','o','u'])
def dfs(st,d,beforeidx):
    global mo,za    
    #문자열의 길이가 L이고 모음과 자음의 조건이 충족되었다면
    if len(st)==l:
        if mo>=1 and za>=2:
            print(st)
        return
    for x in range(d,c):
        #방문하지 않았고 이전 방문 알파벳보다 현재 알파벳의 숫자가 높다면
        if not visited[x] and alpha[x][1]>=beforeidx:
            #모음일 때
            if alpha[x][0] in mos:
                visited[x]=True
                mo+=1
                st+=alpha[x][0]
                dfs(st,d+1,alpha[x][1])
                mo-=1
                visited[x]=False
                st=st[:-1]
            #자음일 때
            else:
                visited[x]=True
                za+=1
                st+=alpha[x][0]
                dfs(st,d+1,alpha[x][1])
                za-=1
                visited[x]=False
                st=st[:-1]
dfs(s,0,-1)            
  

아이디어:

1.알파벳들을 먼저 정렬한다.
2.그 후 알파벳 순서에 대응하는 리스트를 만들고 False로 초기화한다.
3.모음과 자음을 세면서 백트랙킹을 돌린다.
4.방문을 안했고 이전 알파벳보다 순서가 뒤라면 방문처리한다.
5.자음이 1개이상 모음이 2개 이상 깊이가 c가 되면 문자열을 출력한다.

시간복잡도

#n이 12정도 되는 것 같다. 시간에 따라서 될 수도 있고 안 될수도 있을 것 같다.

자료구조

#1차원 리스트:알파벳 & 방문확인리스트, set:모음 집합(set의 탐색은 O(1))

걸린 시간

42:44

총평

백트랙킹 문제 중 골드 난이도를 풀이를 보지 않고 첫 시도에 처음으로 풀게된 문제이다.
문제들을 풀어보며 얻었던 자잘한 기술들을 사용할 수 있었고 덕분에 시간복잡도, 공간복잡도 또한 많이 줄일 수 있었던 좋은 문제이다.