231113 LeetCode 문제 풀이

2785. Sort Vowels in a String

https://leetcode.com/problems/sort-vowels-in-a-string/description/?envType=daily-question&envId=2023-11-13

 

1) 문제 설명

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".

 

2) 제한 사항

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

 

3) 도전 과제

X

 

4) 풀이

첫 순회 때 모음(A,E,I,O,U,a,e,i,o,u)만 찾아서 뽑아낸 후에 빈 자리들에 순서대로 모음을 넣으면 된다.

 

처음에는 모음들을 모은 후 정렬하려 했지만, 시간 복잡도를 줄이기 위해 배열을 여러 개 생성하여 인덱스의 위치와 각 모음의 갯수를 기록하였다.

 

배열을 여러 개 사용해서 메모리 사용률은 상대적으로 높지만, 대신 시간을 크게 줄일 수 있었다.

 

코드 가독성은... 걸리는 시간을 유지한 채로 이 문제에서 어떻게 줄여야 할 지는 잘 모르겠다. 

 

5) 소스 코드 및 결과

class Solution {
    public String sortVowels(String s) {
        char[] charArray = s.toCharArray();
        char[] charResult = new char[s.length()];

        // 모음용 배열. A,E,I,O,U,a,e,i,o,u 순
        int[] vowelArray = new int[10];

        // 인덱스 기록용 배열
        int[] indexArray = new int[s.length()];
        int index = 0;
        int count = 0;

        // 배열 순회
        for(char chr : charArray) {
            switch (chr) {
                case 'A' -> {
                    vowelArray[0]++;
                    indexArray[count++] = index++;
                }
                case 'E' -> {
                    vowelArray[1]++;
                    indexArray[count++] = index++;
                }
                case 'I' -> {
                    vowelArray[2]++;
                    indexArray[count++] = index++;
                }
                case 'O' -> {
                    vowelArray[3]++;
                    indexArray[count++] = index++;
                }
                case 'U' -> {
                    vowelArray[4]++;
                    indexArray[count++] = index++;
                }
                case 'a' -> {
                    vowelArray[5]++;
                    indexArray[count++] = index++;
                }
                case 'e' -> {
                    vowelArray[6]++;
                    indexArray[count++] = index++;
                }
                case 'i' -> {
                    vowelArray[7]++;
                    indexArray[count++] = index++;
                }
                case 'o' -> {
                    vowelArray[8]++;
                    indexArray[count++] = index++;
                }
                case 'u' -> {
                    vowelArray[9]++;
                    indexArray[count++] = index++;
                }
                default -> charResult[index++] = chr;
            }
        }

        for(int vowelIndex : indexArray){
            if(vowelArray[0] > 0){
                charResult[vowelIndex] = 'A';
                vowelArray[0]--;
                continue;
            }

            if(vowelArray[1] > 0){
                charResult[vowelIndex] = 'E';
                vowelArray[1]--;
                continue;
            }

            if(vowelArray[2] > 0){
                charResult[vowelIndex] = 'I';
                vowelArray[2]--;
                continue;
            }

            if(vowelArray[3] > 0){
                charResult[vowelIndex] = 'O';
                vowelArray[3]--;
                continue;
            }

            if(vowelArray[4] > 0){
                charResult[vowelIndex] = 'U';
                vowelArray[4]--;
                continue;
            }

            if(vowelArray[5] > 0){
                charResult[vowelIndex] = 'a';
                vowelArray[5]--;
                continue;
            }

            if(vowelArray[6] > 0){
                charResult[vowelIndex] = 'e';
                vowelArray[6]--;
                continue;
            }

            if(vowelArray[7] > 0){
                charResult[vowelIndex] = 'i';
                vowelArray[7]--;
                continue;
            }

            if(vowelArray[8] > 0){
                charResult[vowelIndex] = 'o';
                vowelArray[8]--;
                continue;
            }

            if(vowelArray[9] > 0){
                charResult[vowelIndex] = 'u';
                vowelArray[9]--;
                continue;
            }

            break;
        }

        String result = String.valueOf(charResult);
        return result;
    }
}

 

6) 다른 사람의 풀이

class Solution {
    public String sortVowels(String s) {
        // Step 1: Collect vowels and sort them in descending order
        List<Character> vowels = new ArrayList<>();
        for (char c : s.toCharArray()) {
            if ("aeiouAEIOU".indexOf(c) != -1) {
                vowels.add(c);
            }
        }
        Collections.sort(vowels, Collections.reverseOrder());

        // Step 2: Construct the answer string by replacing vowels in sorted order
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if ("aeiouAEIOU".indexOf(c) != -1) {
                result.append(vowels.get(vowels.size() - 1));
                vowels.remove(vowels.size() - 1);
            } else {
                result.append(c);
            }
        }

        // Step 3: Return the final string
        return result.toString();        
    }
}

코드 가독성은 높지만, 걸리는 시간이 약 8배 차이난다.