[알고리즘] LeetCode_#345

345. Reverse Vowels of a String

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

🚨 Constraints

▶︎ 풀이

1. 문자열 s 를 뒤집은 문자열 reverse 를 저장
2. 문자열 reverse 의 모음을 순서대로 reverseVowels에 저장
3. 문자열 s 를 순차 탐색하며 해당 문자가 모음(vowels)인 경우 해당 인덱스의 문자를 reverseVowels의 첫번째 문자로 치환하여 result에 저장
4. reverseVowels의 첫번째 문자는 pop 시킨다.
5. 해당 문자가 모음이 아닌 경우, s의 해당 인덱스 문자를 result에 저장

▶︎ 기존코드

class Solution {
    public String reverseVowels(String s) {
        String vowels = "aeiouAEIOU";
        StringBuffer reverse = new StringBuffer(s).reverse();
        StringBuffer reverseVowels = new StringBuffer();
        StringBuffer result = new StringBuffer();
        for (int i = 0; i < reverse.length(); i++) {
            if(vowels.contains(String.valueOf(reverse.charAt(i)))) {
                reverseVowels.append(reverse.charAt(i));
            }
        }

        for (int i = 0; i < s.length(); i++) {
            if(vowels.contains(String.valueOf(s.charAt(i)))) {
                result.append(reverseVowels.charAt(0));
                reverseVowels.deleteCharAt(0);
            } else {
                result.append(s.charAt(i));
            }
        }
        return result.toString();
    }
}

▶︎ 개선사항

실행속도(Runtime), 메모리 효율(Memory)

많은 문자열 변수, 비효율적 반복문 사용으로 느린 속도와 메모리 효율이 떨어짐 → two-pointer 를 활용하여 탐색 시간 및 문자열 위치 전환

• 포인터 1. 문자열 시작 위치 (start)
• 포인터 2. 문자열 끝 위치 (end)
  이 두 포인터를 서로에게로 이동(start++, end--)하며 문자열 중간에서 만날 때(start >= end) 까지 루프 내부 실행

루프 내부

1. 시작 포인터가 모음 문자를 가리킬 때 까지 포인터 이동
2. 끝 포인터가 모음 문자를 가리킬 때 까지 포인터 이동
3. 각 포인터가 모두 모음을 가리키고 있으면 발견된 모음을 서로 바꿈
4. 포인터끼리 모음 위치를 바꾸고 난 후 포인터 start, end 이동

루프가 끝나면 단어 배열에 모음이 반전된 문자열(reverseVowels)이 포함됨

▶︎ 수정코드

class Solution {
    public String reverseVowels(String s) {
        char[] word = s.toCharArray();
        int start = 0;
        int end = s.length() - 1;
        String vowels = "aeiouAEIOU";
        
        while (start < end) {
            // Move start pointer until it points to a vowel
            while (start < end && vowels.indexOf(word[start]) == -1) {
                start++;
            }
            
            // Move end pointer until it points to a vowel
            while (start < end && vowels.indexOf(word[end]) == -1) {
                end--;
            }
            
            // Swap the vowels
            char temp = word[start];
            word[start] = word[end];
            word[end] = temp;
            
            // Move the pointers towards each other
            start++;
            end--;
        }
        
        String answer = new String(word);
        return answer;
    }
}