문제 소개
숫자 n이 주어졌을 때, 모음(a, e, i, o, u)으로만 이루어진 길이 n의 문자열 중에서 사전순(lexicographical order)으로 정렬된 문자열의 개수를 구하는 프로그램을 만들어 보겠습니다. 여기서 문자열 s가 사전순으로 정렬되어 있다는 것은, 모든 유효한 인덱스 i에 대해 s[i]가 s[i+1]과 같거나 알파벳 순서상 그보다 앞에 위치한다는 뜻입니다.
예를 들어 n = 2가 입력으로 주어지면 출력은 15가 됩니다. ["aa", "ae", "ai", "ao", "au", "ee", "ei", "eo", "eu", "ii", "io", "iu", "oo", "ou", "uu"]처럼 조건을 만족하는 문자열이 정확히 15개 존재하기 때문입니다.
해결 전략
이 문제는 동적 계획법(Dynamic Programming)과 누적 합을 활용하면 선형 시간 안에 풀 수 있습니다. 길이가 짧은 문자열부터 시작해, 각 모음으로 끝나는 유효한 문자열의 개수를 배열에 기록하면서 길이를 한 칸씩 늘려 가는 방식입니다.
알고리즘의 진행 순서는 다음과 같습니다.
- n이 1이라면 "a", "e", "i", "o", "u" 다섯 가지뿐이므로 5를 반환합니다.
- 크기가 6인 배열 count를 만들고 모든 요소를 1로 초기화합니다.
- i를 3부터 n까지 반복하며 배열을 다음과 같이 갱신합니다.
- count[1] = count[1] + count[2] + count[3] + count[4] + count[5]
- count[2] = count[2] + count[3] + count[4] + count[5]
- count[3] = count[3] + count[4] + count[5]
- count[4] = count[4] + count[5]
- total을 0으로 초기화한 뒤, i를 1부터 5까지 반복하며 total에 i × count[i]를 더합니다.
- 최종 total 값을 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
def solve(n):
if n == 1:
return 5
count = [1 for i in range(6)]
for i in range(3, n + 1):
count[1] = count[1] + count[2] + count[3] + count[4] + count[5]
count[2] = count[2] + count[3] + count[4] + count[5]
count[3] = count[3] + count[4] + count[5]
count[4] = count[4] + count[5]
total = 0
for i in range(1, 6):
total += i * count[i]
return total
n = 2
print(solve(n))
입력
2
출력
15
알고리즘이 동작하는 이유
핵심은 "각 모음으로 끝나는 정렬된 문자열의 개수"를 단계별로 누적해 가는 것입니다. 정렬된 문자열 맨 뒤에 새 모음을 붙일 때는, 그 모음이 바로 앞 문자보다 사전순으로 같거나 뒤에 와야 한다는 제약이 있습니다. 따라서 매 반복마다 뒤쪽 인덱스의 값들이 앞쪽 인덱스 값들에 더해지는 형태로 배열이 갱신되며, 이 과정을 반복하면 길이 n인 문자열의 전체 경우의 수를 얻을 수 있습니다.
참고로 이 문제는 조합론 관점에서도 해석할 수 있습니다. 길이 n의 비내림차순(non-decreasing) 모음 문자열의 개수는 중복조합 공식에 따라 C(n+4, 4)와 같습니다. 실제로 n = 2일 때 C(6, 4) = 15, n = 3일 때 C(7, 4) = 35로 위 알고리즘의 결과와 일치합니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 고정 크기의 배열만 사용하므로 공간 복잡도는 O(1)입니다. n이 커져도 빠르게 답을 구할 수 있다는 점이 큰 장점입니다.