[LeetCode/Kotlin]Easy - 345. Reverse Vowels of a String

LeetCode - The World's Leading Online Programming Learning Platform

 

문제

Given a string s, reverse only all the vowels in the string and return it.

The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in both lower and upper cases, more than once.

Example 1:

Input: s = "hello"
Output: "holle"

Example 2:

Input: s = "leetcode"
Output: "leotcede"

Constraints:

• 1 <= s.length <= 3 * 105
• s consist of printable ASCII characters.

 

풀이

나의 풀이법

풀이 접근 과정

그냥 모음을 모은 다음에 돌려서 출력하면 되는거 아닌가?

 

최종 소스코드

class Solution {
    fun reverseVowels(s: String): String {
        var answer = ""
        var index = 0
        val vowels = mutableListOf<Char>()

        s.forEach {
            if (isVowels(it)) vowels.add(0,it)
        }

        s.forEach {
            if (isVowels(it)) {
                answer += vowels[index]
                index++
            } else {
                answer += it
            }
        }
        
        return answer
    }

    private fun isVowels(c: Char) = 
        c=='a' || c=='e' || c=='i' || c=='o' || c=='u' || 
        c=='A' || c=='E' || c=='I' || c=='O' || c=='U'
}

반복문을 이용하여 s에서 모음을 뽑아내고 역으로 저장한다.

(뽑아낸 모음을 제일 앞에 저장)

새로 만들어내는 문자에서 모음만 vowels에서 순서대로 꺼내 저장한다.

다른 풀이법

fun reverseVowels(s: String): String {
    // 문자열을 문자 배열로 변환
    val charArray = s.toCharArray()
    
    // 모음을 담을 Set 생성
    val vowels = setOf('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U')
    
    var left = 0
    var right = s.length - 1
    
    while (left < right) {
        // 왼쪽 포인터가 모음을 가리킬 때까지 오른쪽으로 이동
        while (left < right && charArray[left] !in vowels) {
            left++
        }
        
        // 오른쪽 포인터가 모음을 가리킬 때까지 왼쪽으로 이동
        while (left < right && charArray[right] !in vowels) {
            right--
        }
        
        // 왼쪽 포인터와 오른쪽 포인터가 모두 모음을 가리키면 두 문자 교환
        if (left < right) {
            val temp = charArray[left]
            charArray[left] = charArray[right]
            charArray[right] = temp
            left++
            right--
        }
    }
    
    // 문자 배열을 다시 문자열로 변환하여 반환
    return String(charArray)
}

모음을 역순으로 뒤집은 후 문자열 반환한다.

이 솔루션은 투 포인터 알고리즘을 사용하고 있다.

투 포인터 알고리즘은 일반적으로 배열 또는 문자열과 같은 순차 데이터 구조에서 두 개의 포인터(인덱스)를 사용하여 데이터를 조작하거나 검색하는 데 유용한 알고리즘이다.

1. 나의 솔루션 (리스트 사용):
   • 시간 복잡도: O(n^2) - 문자열을 두 번 반복하며 모음을 추출하고, 그 후에 다시 문자열을 만든다.
   • 공간 복잡도: O(n) - 모음을 저장하기 위한 추가 리스트 사용
2. 다른 솔루션 (투 포인터 사용):
   • 시간 복잡도: O(n) - 문자열을 한 번만 반복하면서 모음을 역순으로 뒤집는다.
   • 공간 복잡도: O(1) - 추가 공간을 사용하지 않음.

 

---

Comment

내가 작성한 코드는 효율성 면에서 떨어지는 코드이다.