LeetCode 791. Custom Sort String

https://leetcode.com/problems/custom-sort-string/description/

 

 

난이도: Medium

 

* DS&A 01 Mar

 

 

내 풀이

class Solution {
    public String customSortString(String order, String s) {
        int pointer = 0;
        char[] ca = s.toCharArray();

        for(char c: order.toCharArray()){
            for(int i=pointer; i<ca.length; i++){
                if(ca[i]==c){
                    ca[i] = ca[pointer];
                    ca[pointer++] = c;
                }
            }
        }

        return String.valueOf(ca);
    }
}

 

pointer 변수를 하나 두고

order의 앞 문자부터 찾아서 pointer 위치의 캐릭터와 자리바꾸고 pointer 이동

이렇게 하면 pointer의 앞쪽은 정렬된 상태이므로 다음 반복문에서는 앞쪽을 안봐도 됨

 

 

* order 함수를 만들어서 사용하는 방법도 있으나 정렬 빅오가 커서 성능 낮음

 

* HashTable (또는 char[26])으로 알파벳 빈도수 체크하여 O(n)으로 하는 방법도 있음

 -> Bucket Sort 사용 (이게 정석인듯)

class Solution {
    public String customSortString(String order, String s) {
        int[] ca = new int[26];
        
        // s에 나온 전체 문자들의 빈도 체크
        for(int i=0; i<s.length(); i++){
            ca[s.charAt(i)-'a']++;
        }

        // order에 나온 문자들 먼저 순서대로 append
        StringBuilder sb = new StringBuilder();
        for(char c : order.toCharArray()){
            while(ca[c-'a']-- > 0){
                sb.append(c);
            }
        }
        
        // 나머지 문자들 append
        for(int i=0; i<ca.length; i++){
            while(ca[i]-- > 0){
                sb.append(Character.toString('a'+i));
            }
        }

        return sb.toString();
    }
}