백준 1759번(파이썬):암호 만들기
백준 1759번 문제 정리글 입니다.
문제 출처-https://www.acmicpc.net/problem/1759
문제 내용
나의 풀이
L,C=map(int,input().split())
a=input().split()
def password(a):
for i in range(len(a)):
if len(a)==3:
password(a)=1
elif len(a)>15:
재귀 형식으로 풀기위해 주어진 문자들의 수를 이용하여 제약 조건을 만들어야 한다는 것을 인지했지만 구현할 방법을 찾지 못해서 실패…
알고리즘
- 브루트 포스 문제가 아니라 백트래킹 문제였다고 한다. 사실 두 가지 알고리즘의 개념을 잘 몰라서 개념을 확인하고 풀이를 한번 본 후 다시 문제를 풀어봤다.
알고리즘의 개념
브루트 포스: 검색 대상이 되는 원본 문자열의 처음부터 끝까지 차례대로 순회라며 일일이 비교하는 방식의 알고리즘
백트래킹: 현재 상태에서 가능한 모든 경로를 따라 들어가 탐색하다가, 원하는 값과 불일치하는 부분이 발생하면 더 이상 탐색을 진행하지 않고 전 단계로 돌아가는, 즉 이름 그대로 방금 왔던 길을 되짚어가는, backtrack 하는 알고리즘
문제 해결
def back_tracking(cnt, idx):
# 암호를 만들었을 때
if cnt == l:
# 모음, 자음 체크
vo, co = 0, 0
for i in range(l):
if answer[i] in consonant:
vo += 1
else:
co += 1
# 모음 1개 이상, 자음 2개 이상
if vo >= 1 and co >= 2:
print("".join(answer))
return
# 반복문을 통해 암호를 만든다.
for i in range(idx, c):
answer.append(words[i])
back_tracking(cnt + 1, i + 1) # 백트래킹
answer.pop()
l, c = map(int, input().split())
words = sorted(list(map(str, input().split())))
consonant = ['a', 'e', 'i', 'o', 'u']
answer = []
back_tracking(0, 0)
암호의 길이까지 제약조건으로 너무 신경써서 문제 해결에 어려움이 있었다. 암호를 만들기 위한 알파벳들을 정렬한 후 중요 제약 조건인 모음과 자음 개수를 이용하여 진행했으면 더 빨리 해결할 수 있었을 것 같다. 백트래킹과 브루트 포스 같은 알고리즘의 정의를 다시한번 공부해볼 수 있는 좋은 기회였다.
