문제
풀이
초기 아이디어
어이없게도 itertools.permutations()를 생각했다. 어차피 정렬을 해주고 중복을 제거해야 하는데. 이 경우 시간 초과가 발생했다.
또 처음에는 L에 따라 만들 수 있는 모든 조합을 만들어놓고 따로 체크하는 함수를 만들어 조건을 만족하는 알파벳 조합만 골라내려고 했다.
하지만 효율적이지 않다 판단하여 다른 방법을 생각했다.
정답 코드
우선 입력받은 알파벳 중에서 모음과 자음을 분리했다. 이후 모음이 '1개 ~ 전체 길이-2개'일 때 남은 개수만큼의 자음을 합치는 방식으로 진행했다.
예를 들어 L == 5라면 모음은 최소 1개부터 최대 3개까지 존재할 수 있다.(자음이 최소 2개 존재해야 하므로) 이 경우 모음이 1개일때(자음이 4개), 모음이 2개일 때(자음이 3개), 모음이 3개일 때(자음이 2개) 각각의 조합들을 만들었다.
또 정렬이 되어야 한다는 조건에 맞춰서 적절한 곳에 sorted()를 넣었다.
그리고 itertools.combinations()를 사용했다.
import itertools
L, C = map(int, input().split())
alpha = input().split()
vowels = [a for a in alpha if a in ['a', 'e', 'i', 'o', 'u']] # 전체 모음이 아닌 입력 알파벳 중 모음만
consonants = [a for a in alpha if a not in vowels] # 마찬가지로 입력 알파벳 중 자음만(모음이 아닌 것)
possibles = []
for i in range(1, L - 1): # 1 ~ L-2 개의 모음에 대해서
for t1 in itertools.combinations(vowels, i): # 전체 모음들 중 i개의 조합
for t2 in itertools.combinations(consonants, L - i): # 전체 자음들 중 L-i개의 조합
possibles.append(sorted(t1+t2)) # 모음셋, 자음셋 순서로 더해지므로 sorting해준 후 append
possibles = sorted((map(''.join, possibles))) # 알파벳 순이 아니라 모음 순서대로 들어가 있으므로 한번 더 sorting
for p in possibles:
print(p)혹은 아래처럼 쓸 수도 있다.
import itertools
L, C = map(int, input().split())
alpha = input().split()
vowels = [a for a in alpha if a in ['a', 'e', 'i', 'o', 'u']] # 전체 모음이 아닌 입력 알파벳 중 모음만
consonants = [a for a in alpha if a not in vowels] # 마찬가지로 입력 알파벳 중 자음만(모음이 아닌 것)
possibles = []
for i in range(1, L - 1): # 1 ~ L-2 개의 모음에 대해서
possibles += [sorted(c1 + c2) for c1 in itertools.combinations(vowels, i) for c2 in itertools.combinations(consonants, L - i)]
possibles = sorted((map(''.join, possibles))) # 알파벳 순이 아니라 모음 순서대로 들어가 있으므로 한번 더 sorting
for p in possibles:
print(p)후기
문제 조건을 정확하게 읽고 파악하는 것이 중요하다.
BEST? BETTER!