[leetcode]345. Reverse Vowels of a String

문제

주어진 문자열에서 모음(vowels)들만 뒤집어 반환하는 문제입니다. 모음은 'a', 'e', 'i', 'o', 'u' 다섯 가지로 구성되어 있으며, 대소문자를 구분하지 않습니다.

---

풀이

문자열을 처리하기 위해 투포인터를 활용하여 문제를 해결할 수 있습니다. 

1. 주어진 문자열을 리스트로 변환합니다. 이렇게 하면 문자열의 각 문자에 직접 접근하여 값을 변경할 수 있습니다. 파이썬에서 문자열은 불변한 자료형이므로 리스트로 변환하여 가변한 형태로 다루는 것이 유용합니다.
2. 왼쪽 인덱스(left_index)를 문자열의 시작 위치(0)로, 오른쪽 인덱스(right_index)를 문자열의 끝 위치(len(s) - 1)로 초기화합니다.
3. 왼쪽 인덱스와 오른쪽 인덱스가 만나기 전까지 다음 작업을 반복합니다:
   • 만약 왼쪽 인덱스의 문자가 모음이 아니라면, 왼쪽 인덱스를 오른쪽으로 이동하고 다음 반복으로 진행합니다.
   • 만약 오른쪽 인덱스의 문자가 모음이 아니라면, 오른쪽 인덱스를 왼쪽으로 이동하고 다음 반복으로 진행합니다.
   • 만약 왼쪽 인덱스와 오른쪽 인덱스의 문자가 모두 모음이라면, 두 문자를 swap하여 위치를 교환합니다. 그리고 왼쪽 인덱스를 오른쪽으로, 오른쪽 인덱스를 왼쪽으로 이동합니다.
4. 반복이 종료되면 변경된 문자열 리스트를 다시 문자열로 변환하여 반환합니다. 이는 리스트를 문자열로 변환하는 join() 함수를 사용하여 수행할 수 있습니다.

 

시간 복잡도

주어진 문자열의 길이를 N이라고 할 때, 투포인터 알고리즘을 사용하여 모음을 찾고 swap하는 과정은 O(N)의 시간 복잡도를 가집니다. 이외에 문자열을 리스트로 변환하고 다시 문자열로 변환하는 작업은 O(N) 시간이 소요됩니다. 따라서 총 시간 복잡도는 O(N)입니다.

 

 

공간 복잡도

주어진 문자열의 길이를 N이라고 할 때, 문자열을 리스트로 변환하면 O(N)의 공간이 필요합니다. 그 외에는 추가적인 공간을 사용하지 않으므로, 전체 공간 복잡도는 O(N)입니다.

 

코드

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        s = list(s)
        left_index = 0
        right_index = len(s) - 1

        while left_index < right_index:
            if s[left_index].lower() not in vowels:
                left_index += 1
                continue

            if s[right_index].lower() not in vowels:
                right_index -= 1
                continue

            s[left_index], s[right_index] = s[right_index], s[left_index]
            left_index += 1
            right_index -= 1

        return ''.join(s)

 

 

 

참고

• 345. Reverse Vowels of a String