[Leetcode] 345. Reverse Vowels of a String (C++ 풀이)

string이 주어질 때, 모음에 해당하는 문자들을 역으로 배치해보는 문제. 

 

 

문제에 주어진 예시를 보면 뭔말인지 단번에 알 수 있다. 모음 리스트를 주어진 문자열 내에서 역순으로 다시 재배치하는 것. 가장 단순하게 생각해보면, 주어진 문자열에서 모음을 모두 찾아서 리스트를 만들고, 이를 다시 역순으로 바꿔서 문자열에 끼워넣을 수 있다. 하지만 이 방법에서 비효율적일 수 있다고 생각한 점이 (1) 문자와 해당 index를 같이 저장해야 한다는 것과 (2) two-stage라는 것이다.

 

 

결국 문제는 모음을 찾고, 거꾸로 배치만 하면 되는 건데, 주어진 문자열의 앞뒤에서 각각 모음을 탐색하며 서로 위치를 바꾸는 식으로 문제를 해결하도록 투 포인터 알고리즘을 써보기로 생각했다.

 

class Solution {
public:
    string reverseVowels(string s) {
        set<char> vowels = {'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'};

        int left = 0;
        int right = s.length() - 1;

        while (left <= right){
            if (!vowels.contains(s[left])){
                left += 1;
                continue;
            }
            if (!vowels.contains(s[right])){
                right -= 1;
                continue;
            }

            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            left += 1;
            right -= 1;
        }

        return s;
    }
};

 

• 우선, 모음에 대한 set을 정의한다. 모음의 조건을 체크하기 위함이다. 다만, python의 set에선 include를 체크하는게 O(1)이었는데, c++ set의 contains는 O(log n)이다. 어차피 vowels 개수가 대소문자 10개 밖에 안 되니 크게 문제될 건 없다.
• 그리고 left, right 문자열의 맨 앞, 뒤를 가리키는 포인터를 정의한다. while문의 탈출 조건은 두 개의 포인터가 크로스되는 지점이다.
• left, right가 가르키는 문자가 모음이 아니면 계속 위치를 이동시켜주다가, 두 포인터가 모두 모음을 가리킬 때, 두 문자의 위치를 바꿔준다.
• 이렇게 해서 단 한 번의 탐색만으로 문자 탐색 및 위치 변경을 수행할 수 있다.