LeetCode [345]: Reverse Vowels of a String

📌 LeetCode [345]: Reverse Vowels of a String

🔗 문제 링크

---

문제 설명 📄

주어진 문자열 s에서 모음만을 역순으로 정렬한 후 새로운 문자열을 반환하세요.
모음은 영어 소문자와 대문자의 a, e, i, o, u를 포함합니다.

---

문제 접근 방식 📋

1. 모음 탐색 및 저장:
   • 문자열을 순회하며 모음의 위치와 모음 문자를 각각 저장.
2. 모음 역순 정렬:
   • 저장된 모음을 역순으로 정렬.
3. 모음을 원래 위치에 삽입:
   • 저장된 위치를 사용해, 역순으로 정렬된 모음을 해당 위치에 배치.
4. 새로운 문자열 반환:
   • 최종 배열을 문자열로 변환하여 반환.

---

Solution 💻

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = ['a', 'e', 'i', 'o', 'u']
        indexs = []
        arr = []

        for i in range(len(s)):
            if s[i].lower() in vowels:
                indexs.append(i)
                arr.append(s[i])

        answer = list(s)
        arr = list(reversed(arr))

        for ar, i in enumerate(indexs):
            answer[i] = arr[ar]

        return "".join(answer)

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(n))
  • 문자열 순회: (O(n)).
  • 모음 역순 정렬: (O(m)) (m은 모음의 개수, (m \leq n)).
  • 최종적으로 (O(n + m))이며, 이는 (O(n))로 간주 가능.

공간 복잡도 분석 🗄️

• 공간 복잡도: (O(n))
  • 문자열 배열(list(s)), 모음(arr), 위치(indexs) 저장에 사용.

---

리팩토링 🛠️

개선된 코드

class Solution:
    def reverseVowels(self, s: str) -> str:
        vowels = set('aeiouAEIOU')
        s = list(s)
        left, right = 0, len(s) - 1

        while left < right:
            if s[left] in vowels and s[right] in vowels:
                s[left], s[right] = s[right], s[left]
                left += 1
                right -= 1
            if s[left] not in vowels:
                left += 1
            if s[right] not in vowels:
                right -= 1

        return "".join(s)

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도: (O(n))
  • 투 포인터 방식으로 문자열을 한 번만 순회.

리팩토링 후 공간 복잡도 🗄️

• 공간 복잡도: (O(1))
  • 문자열을 배열로 변환하는 데 (O(n)), 추가 배열 없이 모음을 교환.

---