[코딩테스트 일지 - 99클럽] 18일차 - Sort Characters By Frequency

코딩 테스트 준비 일지 18 일차

• 응시 사이트 : LeetCode

• 문제 : Sort Characters By Frequency

• 난이도 : 하

• 풀이시간 : 20m 15s

Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.

Return the sorted string. If there are multiple answers, return any of them.

 Example 1:

Input: s = "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.

Example 2:

Input: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input: s = "Aabb"
Output: "bbAa"
Explanation: "bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

 Constraints:

• 1 <= s.length <= 5 * 105

• s consists of uppercase and lowercase English letters and digits.

문제 풀이 접근

금일 문제 풀이는 문제 자체가 쉬워서 2가지 정도만 생각하고 쉽게 솔루션을 냈던것 같다.
1. a ~ Z 까지 소문자, 26(소문자) + 26(대문자) => 총 52개의 배열을 먼저 갖고 있다가 만나는 문자마다 Plus 해서 조립해서 리턴하는 방식
2. PairCharCount 내부에는 Char , int 하나씩 있다라고 할때,
List<PairCharCount> 내부에 생성해서 갖고 있다가 PairCharCount 의 갯수로 정렬하고, 갯수만큼 새롭게 문자열을 StringBuilder를 사용해서 string 으로 만들고 반환하는 방식
이 두가지 였는데, 1번을 먼저 생각했다가, 정적배열 정렬도 귀찮고 그래서 2번 방식으로 빠르게 풀었다.

문제 풀이 플로우는 아래와 같다.
1. 파라미터 문자열 s 가 들어오면 길이만큼 순회하면서 charList 안에 현재 문자가 있는지 체크한다.
2. 없다면, 그 문자에 대한 PairCharCount 를 생성하고, Count 를 하나 올려준다.
3. 문자열 끝을 순회할때까지 1~2번을 반복한다.
4. charList 를 Count 기준으로 정렬한다.
5. 정렬된 charList 를 앞에서 부터 순회하고, 그 Count 만큼 또 문자를 추가해야하기 때문에 2중 for문으로 작성한다.
6. 만들어진 string 을 반환한다.

정답 작성 코드 (C#)

    public class PairCharCount
    {
        public char key;
        public int count;

        public PairCharCount()
        {
            this.key = 'a';
            this.count = 0;
        }// Default Creator

        public PairCharCount(char key)
        {
            this.key = key;
            this.count = 0;
        }

        public void SetChar(char key)
        {
            this.key = key;
        }

        public void PlusCount()
        {
            ++this.count;
        }
    }

    public class Solution
    {

        List<PairCharCount> charList = new List<PairCharCount>();

        public string FrequencySort(string s)
        {
            StringBuilder sb = new StringBuilder();
            string answer = string.Empty;

            for (int i = 0; i < s.Length; ++i)
            {
                char element = s[i];

                if (charList.Exists(rhs => rhs.key == element) == false)
                    charList.Add(new PairCharCount(element));

                var elementPair = charList.Find(rhs => rhs.key == element);
                elementPair.PlusCount();
            }

            charList.Sort((a1, a2) => a2.count.CompareTo(a1.count));

            for (int i = 0; i < charList.Count; ++i)
            {
                var element = charList[i];

                for (int j = 0; j < element.count; ++j)
                    sb.Append(element.key);
            }

            answer = sb.ToString();
            return answer;
        }
    }

코드 결과