리트코드 - 345. Reverse Vowels of a String

https://leetcode.com/problems/reverse-vowels-of-a-string/description/

Reverse Vowels of a String - LeetCode

문자열 s가 주어지면 문자열의 모든 모음만 반전하여 반환한다.
모음은 'a', 'e', 'i', 'o', 'u'이며 소문자와 대문자 모두에 두 번 이상 나타날 수 있다.

 

처음에 생각했을 때는 반전이라는 의미가 인덱스까지 대칭해서 반전해야 된다는 것으로 이해했다.

"hello" 인 경우 e는 인덱스 1에 위치하므로 그에 대칭하는 인덱스는 인덱스 3이므로 해당 인덱스에 위치한 문자와 변경해야 한다는 것으로 이해했다.

 

하지만 그렇진 않고 왼쪽에서 첫번째로 등장한 모음 <-> 오른쪽에서 첫번째로 등장한 모음끼리 swap을 시킨 문자열을 반환하는 문제였다.

이 문제를 해결하기 위해 문자열을 리스트로 변환하고, 투 포인터를 사용했다. (왼쪽, 오른쪽)

 

각 포인터가 서로 만나는 지점까지 진행하도록해서 (while l < r) 시간복잡도를 O(n)이 되도록 하였다.  이 때 n은 입력 문자열 s의 길이이다.

이후 포인터를 한 칸씩 이동시키면서 두 글자 모두 모음이 될 경우 언패킹 구문을 활용해서 두 인덱스의 값을 바꿔주도록 한다.

 

이런 식으로 반복한 후 해당 리스트를 join을 활용해서 문자열로 변환한 다음 반환하여 주면 된다.

 

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"]
        l, r = 0, len(s) - 1
        s = list(s)

        while l < r:  # O(n)은 len(s)
            while l < r and s[l] not in vowels:  # O(vowels)
                l += 1
            while l < r and s[r] not in vowels:  # O(vowels)
                r -= 1

            s[l], s[r] = s[r], s[l]  # O(1)
            l += 1
            r -= 1

        return "".join(s)  # O(n)

 

시간 복잡도

시간 복잡도는 O(n)이며, 여기서 n은 문자열의 길이입니다.

공간 복잡도

공간 복잡도는 문자열을 리스트로 변환하는 데 O(n)이 필요하다.