소문자 알파벳으로만 구성된 문자열이 주어졌다고 가정해 봅시다. 이때 찾아야 할 것은 모든 모음(a, e, i, o, u)을 적어도 한 번씩 포함하면서, 자음은 하나도 없는 부분 문자열입니다.
예를 들어 입력 문자열이 "helloworldaeiouaiunicestring"이라면, 조건을 만족하는 부분 문자열은 다음과 같습니다.
aeiou
aeioua
aeiouai
aeiouaiu
eioua
eiouai
eiouaiu
문제 해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- 문자열의 길이를 n에 저장합니다.
- 0부터 n-1까지의 각 시작 인덱스 i에 대해 아래 과정을 반복합니다.
- 모음의 등장 여부를 기록할 새로운 딕셔너리 my_map을 생성합니다.
- i부터 n-1까지의 각 인덱스 j에 대해 다음을 수행합니다.
- s[j]가 모음이 아니라면 내부 반복문을 즉시 종료합니다.
- my_map[s[j]] = 1로 설정하여 해당 모음의 등장을 기록합니다.
- my_map의 크기가 5가 되면(즉, 모든 모음이 등장했다면) s[i:j+1]을 출력합니다.
구현 예제
다음 파이썬 코드를 통해 동작 방식을 더 쉽게 이해할 수 있습니다.
def isVowel(x):
if x in ['a','e','i','o','u']:
return True
return False
def get_substrings(s):
n = len(s)
for i in range(n):
my_map = dict()
for j in range(i, n):
if (isVowel(s[j]) == False):
break
my_map[s[j]] = 1
if (len(my_map) == 5):
print(s[i:j + 1])
s = "helloworldaeiouaiunicestring"
get_substrings(s)
입력
"helloworldaeiouaiunicestring"
출력
aeiou
aeioua
aeiouai
aeiouaiu
eioua
eiouai
eiouaiu
동작 원리 정리
외부 루프는 부분 문자열의 시작 위치를 결정하고, 내부 루프는 자음을 만나기 전까지 연속된 모음들을 순서대로 탐색합니다. 딕셔너리의 크기가 5가 되는 순간, 그 시점까지의 부분 문자열이 '모든 모음 포함 + 자음 없음' 조건을 충족하므로 결과로 출력됩니다. 이 알고리즘의 시간 복잡도는 O(n²)이며, 문자열 길이가 크지 않은 경우 효율적으로 동작합니다.