May LeetCoding Challenge[Day22] - Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Input: "tree"
Output: "eert"

Explanation: 'e' appears twice while 'r' and 't' both appear once. So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 우선, 정말 단순하게 생각했다.

 - 앞에서부터 counting을 하고, counting한 문자에 대한 max를 찾아서 하나씩 retunr하는 것이다.

 - t:1, r:1, e:2와 같이 map을 사용할 것이고, map을 탐색해서 max값을 찾아서 보여줄 것이다.

 - 속도를 빠르게 하기 위해서 중점적으로 생각한 것은 map의 크기이고, ascii 코드의 값을 보니 0-z까지 문자가 나올 때, z는 122이기 때문에 배열의 크기를 123으로해서 문자를 담기로 했다.

 

2. 알고리즘 작성 중, 어려운 점 & 깨달은 점

 

 - 없다.

 

3. 내가 작성한 알고리즘

 

 

class Solution {
    public String frequencySort(String s) {
        char[] sChars = s.toCharArray();
        char[] map = new char[123];
        StringBuilder answer = new StringBuilder();
        for(int i=0; i<sChars.length; i++){
            map[sChars[i]]++;
        }
        for(int i=0; i<map.length; i++){
            int max = 0;
            int maxIndex = -1;
            for(int j=0; j<map.length; j++){
                if(max < map[j]){
                    max = map[j];
                    maxIndex = j;
                }
            }
            if(maxIndex>-1){
                for(int r = 0; r<map[maxIndex]; r++){
                    answer.append((char)(maxIndex));    
                }
                map[maxIndex] = 0;
            }
        }
        return answer.toString();
    }
}

 

4. 결과