99클럽 코테 스터디 31일차 TIL Sort Characters By Frequency feat. Comparator vs Comparable

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

 

 

getOrDefualt

priorityQueue

maxHeap

mapEntry

 

 

 

1.  문제 및 접근

 

 

 

주어진 s를 나타나는 빈도수에 대해 내림차순으로 반환

같은 수의 빈도라면 위치 상관 x , 붙어있어야 함

 

최대 50만 들어오고, 소문자 대문자 둘다 들어옴

 

문자를 돌면서 숫자를 세기 ? 그 후 객체로 비교 해서 정렬compator

map에 저장하고, 그 빈도수로 찾으면 더 편할듯 ?

map에 키로 그 char 넣고, value로 빈도를 넣음

밸류 값으로 내림순 정렬 후 그 키 그대로 반환

 

map.entry와 우선순위 큐 둘다 써 봐야겠다..

 

 

Constraints:

• 1 <= s.length <= 5 * 10^5
• s consists of uppercase and lowercase English letters and digits.

 

 

 

 

 

 

2.  풀이

 

public String frequencySort(String s) {

    HashMap<Character, Integer> map1 = new HashMap<>();


    StringBuilder sb = new StringBuilder();



    for (int i = 0; i < s.length(); i++) {
        char now = s.charAt(i);
        map1.put(now, map1.getOrDefault(now, 0) + 1);


    }





    PriorityQueue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>( // 우선순위 큐 사용
            (a, b) -> b.getValue() - a.getValue()
    );
    maxHeap.addAll(map1.entrySet());

    while (!maxHeap.isEmpty()) {
        Map.Entry<Character, Integer> entry = maxHeap.poll();
        char c = entry.getKey();
        int count = entry.getValue();
        for (int i = 0; i < count; i++) {
            sb.append(c);

        }

    }

    List<Map.Entry<Character, Integer>> list = new ArrayList<>(map1.entrySet()); // 일반적인 리스트 사용



    list.sort((a, b) -> b.getValue().compareTo(a.getValue()));


    for (Map.Entry<Character, Integer> entry : list) {
        char key = entry.getKey();
        int count = entry.getValue();
        for (int i = 0; i < count; i++) {
            sb.append(key);
        }
    }


    return sb.toString();
}

 

 

 

 

일단 map에 넣고, 찾을 때 반환 하는 게 훨씬 빠르다고 생각했고

 

처음엔 key, value 값을 Integer, Character로 넣고 같은 value가 들어오면 key 값을 증가시키려고 했으나,

 

찾을 땐 편해보이지만, 넣을 때 애를 먹어서 그냥

 

Charater, Integer의 형태로 넣어야겠다.

 

 

 

 

map.entry 방식과 우선순위 큐로 구현을 하겠다.

 

 

 

 

 

2-1. map 저장

 

 

 

ex) String s = "tree"

 

 

key = Character, value = Integer 타입의 map을 선언해주고,

 

정답을 담을 StringBuilder

 

1. 반복문을 돌며, 현재 char 타입의 now의  map 에다 넣는다.
2. 현재 key값이 map 없으니까 key에다가 value로 default 값인 0을 넣는다.
3. 현재 now로된 key가 있다면 ? 그 key의 value를 가져와 1을 더해준다.

 

getOrDefault는 현재 key값이 없다면 value 값에 내가 정한 defaultValue를 넣는다고 알면 된다.

있다면 내가 해줄 것을 정하면 되는데 나는 그 value 값에 +1을 해줄 것.

그래야 중복으로 나올 때 마다 + 되니까

 

 

 

 

 

 

 

 

2-2. map.entry

 

 

 

 

entry라는 객체는 hashMap에 대한 key-value 쌍을 하나의 객체로 갖고 있어 getKey(), getValue() 메서드로 key와 value에 접근할 수 있도록 해줘서 편리

 

 

 

 

Map.Entry 메서드

 

• getKey() : Map.Entry 객체의 key를 가져올 수 있다.
• getValue() : Map.Entry 객체의 value를 가져올 수 있다.
• setValue(value) : Map.Entry 객체의 key 값에 대한 value를 수정 할 수 있다.

 

 

 

 

주요 장점

 

1. map은 key, value를 따로 따로 접근해야 하지만 한번에 묶어 접근이 편리하다.
2. value 수정 시 key에 접근 후 value를 수정하고 다시 저장하는 형태를 setValue로 간편하게 가능하다

 

 

 

 

 

 

 

 

 

2-3.  정렬

 

 

 

정렬하기 위해 map.Entry 타입의 list를 선언 (map1.enrtySey()을 전달)

 

 

정렬 과정에서 람다식을 쓴다. 

1.  

 

(a,b) -> b.getValue()로 b의 값을 compareTo 함수로 a.getValue()로 a값과 비교

 

 

 

 

 

 

 

정렬은 정해져있다. 오름차순이 기준이라 음수가 무조건 앞으로라고 외우면 됨!

 

간단하게 작은 수는 앞이다.

 

 

 

b를 기준으로 a를 비교하기에 

 

 

 

b가 더 크다면 ? 

• 양수 반환

a가 더 크다면 ?

• 음수 반환

같다면 ?

• 0 반환

 

 

b가 더 크다고 가정한다면 양수를 반환하기에 b가 a보다 더 앞에 있을 것이다.

 

 

더 작은 게 앞인데, b를 기준으로 잡았으니 양수가 앞에 있을 것!

 

 

 

첫 번째 인자를 두 번째 인자보다 작다고 간주할 때, 첫 번째 인자를 두 번째 인자보다 앞에 위치시키는 것

 

 

첫 번째 인자 b가 a보다 작으면, 첫 번째 인자를 앞에 위치시킨다.

첫 번째 인자 a가 b보다 작으면, 첫 번째 인자를 앞에 위치시킨다.

 

 

 

그러므로 오름차순으로 만들고 싶다면 a를 기준을 a.compareTo()을 부르면 된다.

 

 

 

 

 

 

 

 

2-4. 정렬된 순서로 StringBuilder 추가

 

 

 

우리가 만든 list를 아까와 같은 type의 entry로 만든 후

 

key에 key  

count에 value를 저장해준다.

 

그리고 value를 기준으로 map에서 정렬된 순서기에 

ex) "tree"의 경우 

 

map {key = e, value = 2}

         {key = t, value = 1}

         {key = r, value = 1}

 

 

(제한사항에서 같은 빈도 수의 1인 t나 r은 순서 상관없다고 했고, r이 먼저 있을 수도 있다)

 

 

 

그러므로 count만큼 돌면서 key를 StringBuilder에 추가해주면

 

 

 

 

"eetr" 혹은 "eert"의 값이 저장된다.

 

 

 

 

 

 

 

 

3.  priority Queue 사용

 

 

 

 

우선 순위 큐라고 불리는 priority Queue 전에 멘토님이 정렬의 추천으로 말씀하셔서 사용해보자.

 

 

maxHeap과 minHeap이 대표적

 

 

 

priority Queue? 

 

• 우선순위 기반 저장: 요소들은 우선순위에 따라 저장되며, 우선순위가 높은 요소가 먼저 나오게 됨
• 힙 구조: PriorityQueue는 보통 힙(Heap)이라는 자료구조를 기반으로 구현. 힙은 부모 노드가 자식 노드보다 항상 우선순위가 높거나 같은 완전 이진 트리.
• 삽입 및 삭제 시간 복잡도: 요소의 삽입은 O(log n)의 시간 복잡도를 가지며, 삭제(가장 우선순위가 높은 요소 추출)는 O(log n)의 시간 복잡도를 가짐.

 

 

 

 

시간 복잡도는

 

heap의 경우만 따지자면 O(log n)이다.

 

poll 연산을 하며 최대 힙 속성을 유지하기 위해 O(log n) 시간이 걸리지만, 이걸 n번 반복 해야한다.

 

O(n log n)

 

알파벳은 대문자(26) + 소문자(26) 이니 52 log 52의 값이 나온다.

 

 

 

 

 

 

사용 시 유의사항

 

• PriorityQueue는 스레드 안전하지 않으므로 멀티스레드 환경에서 사용할 때 동기화 필요.
• 기본적으로 정해주지 않으면 Comparable 인터페이스에 따라 정렬, 아까 말한대로 Integer의 경우 오름차순이 default

 

 

 

 

유의사항에 따라 기본으로는 minHeap으로 정렬되니,

 

 

람다식으로 내림차순으로 정렬되게 선언해주고, map.entrySet()을 addAll 해준다.

 

 

 

 

 

 

list와 저장 방식은 같다.

 

 

maxHeap이 빌 때 까지 돌면서

 

entry로된 요소를 하나씩 poll()로 꺼낸 다음,

 

위와 같이 저장

 

 

 

 

 

 

 

사실 큰 차이는 없는 것 같지만, 써본 것에 의미를 두자.

 

 

 

 

 

 

 

위가 list

아래가 priorityQueue

 

 

 

 

 

 

 

번외.  comparable vs comparator

 

 

 

 

 

전에도 포스팅한 적이 있어서 간단하게 하자면,

 

primitive type의 경우 우리는 그냥  >, <, = 같은 기호로 정렬할 수 있다.

 

 

 

하지만 객체를 정렬해야 한다면 ?

 

• Comparable을 사용한 compareTo()
• Comparator을 사용한 compare()

 

 

메소드를 활용하여 두 객체의 대소 비교를 한다는 것이다.

 

 

 

 

둘의 차이점은

 

https://st-lab.tistory.com/243

 

 

전에도 포스팅한 적이 있어서 간단하게 하자면,

 

comparable은 자기 자신과 매개변수를 비교이고,

 

comparator는 두 매개변수 객체를 비교한다.

 

 

 

간단하게 객체에서 여러 매개변수가 존재한다면 comparator를 쓰면 된다.

 

 

 

 

 

 

 

 

4.  마무리

 

 

 

간단하게 구현할 수 있지만, 자료구조들을 되도록 까먹지 않게 여러 개를 써봐야 할 것 같다는 생각이 들었다.

 

하나의 알고리즘 문제를 푸는데도, 무궁무진하게 사용될 수 있고 어떻게 활용할 수 있고, 또 뭐가 더 효율적인지

 

아는 것이 중요한 것 같다..

 

알수록 내가 활용할 수 있는 범위가 넓어지니까..