[백준] #1759 암호 만들기 - 파이썬(python)

[백준] #1759 암호 만들기

> 골드 5 문제

> 문제: https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

> 개념 참고 사이트: https://blog.naver.com/kks227/220786417910

백트래킹(Backtracking) (수정 2019-10-09)

 

 

풀이 방법

1. itertools 사용 ver

2. back tracking 사용 ver

 

 

풀 때 생각해야하는 점

1. 모음개수 & 자음개수 --> 모음개수만 가지고 비교해도 가능 (코드참고)

2. 비밀번호라 들이있는 내용물이 같아도 순서가 달라지면 다른 것임 ! -> 하지만, 알파벳 순이고, 중복되는 것 없으니 내용물 같은 것은 한번만 포함됨 

 

 

 

<1. itertools 사용 ver>

# itertools 사용시
import heapq #넣으면서 sort하려면 사용
from itertools import combinations
import sys


input = sys.stdin.readline
n, s = map(int, input().split())
a= list(input().split())

vowel  = ["a","e","i","o","u"]
ans =[]
# a에서 n개 고르기
for comset in combinations(a,n):
    vcount=0
    # 각 set에서 모음이 몇개인지 count
    for v in vowel:
        if v in comset:
            vcount +=1

    # 모음이 1개이상이고 자음이 2개이상(=모음이 n-2개보다 적거나 같으면 됨)
    if 1<=vcount<=(n-2):
        ans.append("".join(sorted(comset)))
ans.sort()
for an in ans:
    print(an)
print(len(ans))

 

 

<2. back tracking 사용 ver>

모음 유무를 세는 것도 다른 방법으로 구현했습니다.

# itertools 사용시 안하면
from itertools import combinations
import sys

def backtrack(now, pre, nvowel):
    # now: 현재 단계
    # pre: 전단계
    # nvowel: 모음 개수
    
    #개수를 다 채우면 return (그전까지는 계속 재귀)
    if now ==n:
        # 모음자음 개수 맞으면
        if 1<=nvowel<=(n-2):
            print("".join(ans))
        return

    # 다음 글자 정하기
    for i in range(pre+1, s):
        ans[now] = a[i]
        backtrack(now+1, i, nvowel+ isvowel[ord(a[i])-ord('a')])

    

input = sys.stdin.readline

# input 가져오기
n, s = map(int, input().split())
a= list(input().split())
a.sort() # 알파벳 순으로 나열 -> 바로 print하기 위해서


# 모음 set만들기 
vowel = ['a','e','i','o','u']
isvowel =[False]*26
for vv in vowel:
    isvowel[ord(vv)-ord('a')] = True

# 정답 틀 만들기
ans =['0']*n
# backtracking -정답
backtrack(0,-1,0)