[이코테] 암호 만들기

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 백준 링크를 참조하자.

https://www.acmicpc.net/problem/1759

1759번: 암호 만들기

사고과정

• 너무 어렵게 생각했다. 조합을 이용하되 투 포인터를 활용한 합집합 정렬을 이용해야 하는 것 같다고 생각했다. 처음에 조합을 사용하고 모음 처리 로직을 단순히 추가할까? 했는데 시간 복잡도 문제를 생각했다. 그런데 나중에 문제를 보니 L, C의 범위가 15이하 값이라 조합만 이용했어도 충분했다... 반드시 주어진 수의 범위를 보고 알고리즘 설계를 시작하는 습관을 들이자! 쉬운 문제는 어렵게 생각하고 어려운 문제는 쉽게 생각하는 나는 도덕책...🥲 
• 원소를 정렬한 후 조합을 구하게 되면 정렬한 상태를 어기지 않은 상태에서 조합을 만들어내는 것을 기억하자!
• 문자열에 속한 모음 개수를 count하고 자음의 최소 개수도 검증할 수 있도록 처리한 조건문은 인상적이었다. 직관적으로 이해가 안되서 연습장에 써보았다.. 다시 설명하자면 최소 모음 개수는 1개, 최소 자음 개수는 2개니까,  "문자열에서 센 모음 개수 <= 만들 수 있는 암호 문자열 전체 개수 - 최소자음개수(2)" 여야 한다. 예를 들어, 전체 문자열 개수가 6개인데, 모음 개수가 4개로 나왔다. 그러면 4 <= 4 이기 때문에 괜찮지만 모음 개수가 5라면 5 <= 4가 된다. 따라서 모음 개수가 5일 때는 암호로 못만드니까 처리를 할 수 있다.

풀이(스스로 못 푼 풀이)

from itertools import combinations
l, c = map(int, input().split())
vowels = ['a', 'e', 'i', 'o', 'u']
array = list(map(str, input().split()))
array.sort() # 암호는 오름차순으로 정렬되어야 함

for password in combinations(array, l):
    vowel_cnt = 0
    for word in password:
        if word in vowels:
            vowel_cnt += 1
    if vowel_cnt >= 1 and vowel_cnt <= l - 2:  # 자음이 최소 2개있어야 하니까 모음 개수 허용 범위는 <= 전체 개수 - 2이어야 함!
        print(''.join(list(password)))