어이없게도 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)
문제 조건을 정확하게 읽고 파악하는 것이 중요하다.