C++ ] leetCode 2785 - Sort Vowels in a String

 

 

리트코드 2785 문제

 

 

Given a 0-indexed string s, permute s to get a new string t such that:

• All consonants remain in their original places. More formally, if there is an index i with 0 <= i < s.length such that s[i] is a consonant, then t[i] = s[i].
• The vowels must be sorted in the nondecreasing order of their ASCII values. More formally, for pairs of indices i, j with 0 <= i < j < s.length such that s[i] and s[j] are vowels, then t[i] must not have a higher ASCII value than t[j].

Return the resulting string. The vowels are 'a', 'e', 'i', 'o', and 'u', and they can appear in lowercase or uppercase. Consonants comprise all letters that are not vowels.

 

 

Example 1:

• Input: s = "lEetcOde"
• Output: "lEOtcede"
• Explanation: 'E', 'O', and 'e' are the vowels in s; 'l', 't', 'c', and 'd' are all consonants. The vowels are sorted according to their ASCII values, and the consonants remain in the same places.

 

 

Example 2:

• Input: s = "lYmpH"
• Output: "lYmpH"
• Explanation: There are no vowels in s (all characters in s are consonants), so we return "lYmpH".

 

 

Constraints:

• 1 <= s.length <= 105
• s consists only of letters of the English alphabet in uppercase and lowercase.

 

 

아래와 같은 방법으로 풀었다.

 

1. 문자열을 순환하며 모음이 위치한 인덱스를 등장하는 순서대로 idx 벡터에 저장한다.

 

2. 퀵정렬으로 idx 벡터를 오름차순 정렬한다. (해당 인덱스 문자의 아스키코드를 비교) 

 

3. 정렬된 idx 벡터를 기반으로 정렬된 순서의 모음으로 이루어진 문자열 sortedVowels를 뽑아낸다.

 

4. 다시 문자열을 순환하며 모음이 등장하는 경우 sortedVowels로 대치한다.

 

 

class Solution {
public:
    bool isVowel(char c) {
        string vowels = "AEIOUaeiou";
        return vowels.find(c) != string::npos;
    }

    string sortVowels(string s) {
        vector<int> idx;
        for (int i = 0; i < s.length(); i++) {
            if (isVowel(s[i])) {
                idx.push_back(i);
            }
        }

        sort(idx.begin(), idx.end(), [&](int a, int b) {
            return s[a] < s[b];
        });

        string sortedVowels;
        for (int i = 0; i < idx.size(); i++) {
            sortedVowels += s[idx[i]];
        }

        for (int i = 0, j = 0; i < s.length(); i++) {
            if (isVowel(s[i])) {
                s[i] = sortedVowels[j++];
            }
        }

        return s;
    }
};

 

 

 

 

원래는 아래처럼 선택정렬으로 풀었었는데 Time Limit Exceeded 문구가 떠서 위의 방법으로 다시 풀었다.

 

class Solution {
public:
    bool isVowel(char c) {
        string str = "AEIOUaeiou";
        size_t found = str.find(c);
        if(found != string::npos) {
            return true;
        }
        else {
            return false;
        }
    }
    string sortVowels(string s) {
        vector<int> idx;
        for(int i = 0; i< s.length(); i++) {
            if(isVowel(s[i])) {
                idx.push_back(i);
            }
        }

        for(int i = 0; i < idx.size() - 1; i++) {
            for(int j = i + 1; j < idx.size(); j++) {
                if(s[idx[i]] > s[idx[j]]) {
                    char temp = s[idx[i]];
                    s[idx[i]] = s[idx[j]];
                    s[idx[j]] = temp;
                }
            } 
        }
        return s;
    }
};