리트코드 - 451. Sort Characters By Frequency

리트코드 - 451. Sort Characters By Frequency

주어진 문자열을 최다빈도 글자순으로 재배열하는 문제입니다. 빈도수를 기록하기 위해 hashmap을 사용했고, 최다빈도순으로 뽑아내기 위해 priority queue을 사용했습니다. 또한비교를 편하게 하기 위해 FreqChar class를 구현했습니다.

---

string builder

마지막 return 문자열을 만드는 과정에서 처음에는 다음과 같이 구현했더니 통과는 했지만 속도가 너무 느렸습니다.

String ans = "";
for (int i = 0; i < cur.frequency; i++) {
	ans += String.valueOf(cur.c));
}

문자열과 문자열을 더해나가는 방식인데, String이 primitive가 아니라는 사실을 간과하고 있었습니다. StringBuilder를 이용하니 속도가 40배정도 빨라졌습니다.

StringBuilder는 capacity를 갖고 있어 append 할 때 무조건 새로 만드는 것이 아니라 크기를 적절히 늘려가며 동작합니다.

Class StringBuilder - 오라클 링크

...
Every string builder has a capacity. As long as the length of the character sequence contained in the string builder does not exceed the capacity, it is not necessary to allocate a new internal buffer. If the internal buffer overflows, it is automatically made larger.
...

import java.util.*;

class Solution {
    HashMap<Character, Integer> map = new HashMap<>();

    public String frequencySort(String s) {
        PriorityQueue<FreqChar> pq = new PriorityQueue<>();

        for (int i = 0; i < s.length(); i++) {
            char cur = s.charAt(i);

            if (map.get(cur) == null) {
                map.put(cur, 0);
            }
            map.put(cur, map.get(cur) + 1);
        }

        Iterator<Character> keys = map.keySet().iterator();
        while (keys.hasNext()) {
            pq.add(new FreqChar(keys.next()));
        }

		// do not add string one other, but use string builder
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            FreqChar cur = pq.poll();

            for (int i = 0; i < cur.frequency; i++) {
                sb.append(String.valueOf(cur.c));
            }
        }

        return sb.toString();
    }

    class FreqChar implements Comparable<FreqChar> {
        int frequency;
        char c;

        FreqChar(char c) {
            this.frequency = map.get(c);
            this.c = c;
        }

        @Override
        public int compareTo(FreqChar fc) {
            return map.get(fc.c) - map.get(this.c);
        }
    }
}