소문자로 이루어진 문자열이 주어졌을 때, 문자열에 포함된 모음(vowel)들만 골라서 순서를 거꾸로 뒤집는 문제를 생각해 볼 수 있습니다. 예를 들어 문자열이 "hello"라면 모음 'e'와 'o'의 위치를 서로 바꿔 결과는 "holle"이 됩니다. 마찬가지로 "programming"은 "prigrammong"으로 변환됩니다.
이 문제를 해결하기 위한 접근 방식은 다음과 같습니다.
- 주어진 문자열을 순회하면서 모음을 찾아 별도의 리스트에 저장하고, 해당 모음의 인덱스(위치)도 함께 기록합니다.
- 저장된 모음 리스트를 역순으로 뒤집습니다.
- 인덱스 추적용 변수 idx를 0으로 초기화합니다.
- i가 0부터 문자열 길이 - 1까지 반복하면서 다음을 수행합니다.
- 현재 위치 i가 모음 인덱스 목록에 있다면, 뒤집힌 모음 리스트의 vowels[idx] 값을 최종 문자열에 넣고 idx를 1 증가시킵니다.
- 그렇지 않다면 원래 문자열의 해당 문자를 그대로 최종 문자열에 넣습니다.
- 완성된 리스트를 문자열로 합쳐서 반환합니다.
구현 예시
아래 파이썬 코드를 통해 실제 동작 과정을 더 쉽게 이해할 수 있습니다.
class Solution:
def reverseVowels(self, s):
chars = list(s)
index = []
vowels = []
for i in range(len(chars)):
if chars[i] in ['a','e','i','o','u']:
vowels.append(chars[i])
index.append(i)
vowels = vowels[::-1]
final = []
ind = 0
for i in range(len(chars)):
if i in index:
final.append(vowels[ind])
ind += 1
else:
final.append(chars[i])
str1 = ""
return str1.join(final)
ob1 = Solution()
print(ob1.reverseVowels("hello"))
print(ob1.reverseVowels("programming"))입력
"hello" "programming"
출력
holle prigrammong
동작 원리 정리
이 알고리즘의 핵심은 자료구조 두 개를 활용하는 것입니다. 하나는 모음 문자들을 담는 vowels 리스트이고, 다른 하나는 그 모음들이 원래 문자열에서 어느 위치에 있었는지 기록하는 index 리스트입니다. 모음 리스트를 뒤집은 후, 원본 문자열을 처음부터 끝까지 훑으면서 모음이 있던 자리에는 뒤집힌 모음을 순서대로 채워 넣고, 나머지 자리에는 원래 문자를 유지하면 됩니다.
시간 복잡도는 문자열을 두 번 순회하므로 O(n)이며, 공간 복잡도 역시 모음 개수와 최종 리스트 크기에 비례해 O(n)입니다. 참고로 두 포인터(two-pointer) 기법을 사용하면 추가 리스트 없이도 같은 결과를 얻을 수 있어 메모리를 절약할 수 있습니다.