451. Sort Characters By Frequency

문제

https://leetcode.com/problems/sort-characters-by-frequency/description/

풀이

class Solution {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();

        for(char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        List<Character> list = new ArrayList<>(map.keySet());

        list.sort((a,b) -> map.get(b) - map.get(a)); 
		// Collections.sort(list, (a,b) -> map.get(b) - map.get(a));
        // List타입만 정렬 가능
        	
        for(char c : list) {
            for(int i = 0; i < map.get(c); i++) {
                sb.append(c);
            }
        }

        return sb.toString();
        
    }
}

• Map의 key를 List에 넣고, List를 map의 value 기준으로 내림차순 정렬
• list를 돌며 value만큼 sb.append(); - O(1), String에서 일일히 += 해주면 할때마다 새롭게 String을 만듦 -> O(N^2)
• String s의 길이만큼 돌면서 sb.append()를 하므로 이중 포문이더라도 O(N)