암호찾기 백준 9663

우선 문제 해석부터

1. 최조교가 방 열쇠를 주머니에 넣고 서울로 가버림

2. 대안책으로 702호에 새로운 보안 시스템 설치하는데 열쇠가 아니라 암호로 동작

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

4. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 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

 

띵킹해보자~

1. 우선 재귀를 이용해야 할 것 같음.

2. 반복문이 뭔가 많이 생길 것 같음.

 

그렇다면

1. 재귀 함수의 종료 시점부터 지정해야겠다. 종료 시점은? 

2. 보통은 종료 시점이 지정되면 for문이 등장할테고,

3. for 문안에는 각각의 경우에 대해 값을 바꿔가면서 재귀함수를 호출해야겠다.

어떤 경우?

4.그리고 마지막으로 시간 초과가 안되려면 모든 for문을 돌지 않고, 특정 경우에만 실행하도록 가지치기 하자.

 

그리고

이 문제 같은 경우에서 쓰이는 구문들

1. 알파벳별로 찢어버리기

2. 스택을 쌓아서 만약 n 만큼 차게 되면 문자를 반복문을 이용해서 push한다.

 2-1. 스택이 비어있다면?

현재 문자를 스택에 푸쉬하고 백트래킹을 재귀호출해서 pop을 이용해서 다시 빼내야지

 2-2. 스택이 안 비어있다면?

 그럼 조건을 추가해줘서 현재 문자를 스택에 푸쉬하고 백트래킹을 재귀호출하고 pop을 이용해서 다시 빼야지

3. 그럼 이제 print하면 이지~~~

n,m=map(int,input().split())
password=input().split()
password.sort()
answer=[]

def back_tracking():
	
	if len(answer)==n:

		con=0
		vow=0
		for word in answer:
			if word in ['a','e','i','o','u']:
				vow+=1
			else: 
				con+=1

		if vow>=1 and con>=2:
			print(''.join(answer))
		
	else:
    
		for word in password:
			if len(answer)==0:
				answer.append(word)
				back_tracking()
				answer.pop()
			elif answer[-1]<word :
				answer.append(word)
				back_tracking()
				answer.pop()
	
back_tracking()