99클럽 코테 스터디 39일차 TIL Reduce Array Size to The Half

https://leetcode.com/problems/reduce-array-size-to-the-half/

 

 

 

 

그리디

map.merge

 

 

 

 

 

 

1. 문제 및 접근

 

 

1338. Reduce Array Size to The Half

 

배열이 주어지면 배열 안에 있는 수 중 하나를 골라 그 수를 다 없앨 수 있다.

그럴 때 반 이상 줄일 수 있는 최소의 수의 최소 갯수 반환

 

arr = [3,3,3,3,5,5,5,2,2,7]

map으로 찾고, 그 수를 돌면서 반 이상되면 바로 리턴 ? 3 =4 5=3 2=2 7=1

키 값은 상관 없음 번호로 부여하고, 몇개인지가 중요

 

 

 

Constraints:

• 2 <= arr.length <= 10^5
• arr.length is even.
• 1 <= arr[i] <= 10^5

 

 

 

 

 

2.  풀이

 

public int minSetSize(int[] arr) {

    HashMap<Integer, Integer> map = new HashMap<>();


    for (int i = 0; i < arr.length; i++) {
        map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
    }

    int size = map.size();
    Integer index[] = new Integer[size];
    int now = 0;

    for (Integer value : map.values()) {
        index[now++] = value;
    }
    
    Arrays.sort(index, new Comparator<Integer>() {


        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    });


    int sum = 0;
    int count = 0;


    for (int i = 0; i < index.length; i++) {
        sum += index[i];

        if (sum >=arr.length/ 2) {
            count++;
            break;
        }
    }

    return count;

}

 

 

1. map에 key값에 해당하는 숫자와 그 숫자가 몇 번 나왔는지에 대한 value를 담는다.

 

2. 효율적으로 탐색하기 위해 내림차순 정렬

 

3. 누적합 sum에 value들을 더해주며 횟수를 세어준다. size/2이 넘으면 반복문을 빠져 나온다.

 

 

 

 

 

 

 

 

2-1. map

 

 

 

Integer의 key와 Integer의 value를 가지는 map 선언

 

반복문을 돌면서 arr[i]인 key 값에 해당하는 수와 빈도를 세기 위해, getOrDefult

 

설명은 포스팅 했으니 pass

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

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

 

 

 

 

 

 

 

 

 

 

2-2. value를 담을 배열

 

 

 

map에서 빈도 수만 가져와서 저장할 배열 선언하고,

map을 돌면서 배열에 추가해준다.

 

ex) arr= [3, 3, 3, 3, 5, 5, 5, 2, 2, 7}

      index = [2, 4, 3 ,1]

     

 

몇번 있는지가 핵심사항이고, 어떤 수가 몇번 있는 지는 중요하지 않다.

 

그래서 index에는 수들의 빈도 횟수만 저장

 

 

 

 

 

 

 

 

 

 

2-3. 정렬

 

 

 

효율적으로 탐색하기 위해 사실 큰 수부터 판별하는 것이 좋을 것 같았다.

 

(사실 오름차순으로 하고, 뒤에서 부터 찾아도 되지만 내림차순으로 comparator도 써보고 좀 더 직관적이길 원해서..)

 

 

 

정렬 후 index = [4,3,2,1]

 

 

 

 

 

 

2-4. 반보다 크냐 ?

 

 

순서대로 돌면서 sum에다가 현재 index[i] 수를 추가해줌

반복마다 count를 ++ 해주고 

 

현재 sum이 size의 반 이상된다면 반복문 종료 후 return;

 

 

 

 

 

 

 

 

 

 

 

3. 다른 사람 풀이

 

 

 

아니 리트코드에서 /ms별로 다른 사람의 풀이를 볼 수 있다.. 스터디 하다가 누가 누르는 거 봐서 신세계네

 

 

나보다 2배 빠른 풀이법이길래 궁금해서 봤더니

 

 

 

 

며칠 전에 포스팅한 counting Sort 기법이다.

배열의 빈도 수를 cnt로 접근했네.. 나는 왜 이 생각을 하지 못했을까 ?ㅠ

 

근데 약간 코드가 완벽한 counting Sort가 아니긴 한데, 앞으로 정렬의 과정에서 들어 오는 수의 범위가 크지 않다면

countingSort를 떠올려야겠다.

 

 

99클럽 코테 스터디 32일차 TIL Top K Frequent Elements feat. CountingSort

99클럽 코테 스터디 32일차 TIL Top K Frequent Elements feat. CountingSort

 

 

 

 

 

 

4. map.merge()

 

 

 

전에 포스팅할 때 다음에는 gerOrdefault 말고 map.merge를 써봐야겠다고 말했는데 한번 사용해보자..

 

 

 

 

대충 번역해보니까

 

 

 

1. 키가 없거나 null 값인 경우:
   • 지정된 키가 맵에 없거나 키가 null 값과 연결되어 있으면 주어진 값과 연결.
2. 키가 이미 값과 연결된 경우:
   • 지정된 키가 이미 값과 연결된 경우, 주어진 리매핑 함수를 사용하여 값을 새 값으로 대체.
   • 리매핑 함수가 null을 반환하면 해당 키-값 매핑을 맵에서 제거

 

 

 

예시)

map.merge(key, msg, String::concat)

 

 

 

• 키가 존재하지 않으면 msg가 값으로 설정된다.
• 키가 존재하면 기존 값에 msg를 연결하여 새 값으로 설정

 

 

 

 

 

실제 사용을 보자면,

 

 

 

map.merge의 인자로 세 가지를 받는다.

 

1. 키 (Key)
2. 새 값 (Value)
3. 두 값을 병합하는 함수 (BiFunction)

 

 

 

map.merge(key, value, BiFunction)의 BiFunction은 두 값을 입력받아 하나의 값을 반환하는 함수형 인터페이스. 여기서 Integer::sum을 사용하면 두 Integer 값을 더하는 역할

 

 

Integer.sum(int a, int b)를 호출하는데, 키가 있다면,

a = 기존의 존재하는 key 값의 value,  b = 이번에 들어온 value를 넘긴다.

 

(둘다 우리는 1로 지정해놔서 하나씩 계속 더해짐)

 

 

 

아니면 간단한 람다식으로 표현해도 된다 !

 

 

arr = [3, 3, 3, 3, 5, 5, 5, 2, 2, 7]

 

1. arr[0] = 3 , map []
   
   현재 map에 key 값인 3이 없으니 value로 정해진 1로 정해진다.
   
   
   
   
2. arr[1] = 3 , map [3=1, ]
   
   현재 map에 key 값인 3이 있으니 기존 값에 Integer::sum을 사용해서 
   map = [3=2, ]

 

 

이까지만 설명해도 예시를 다 봤으니,, 

 

 

 

 

 

 

 

 

 

 

5.  마무리

 

 

 

 

새로운 함수들과 람다식에도 익숙하져야 한다. 기존의 것들만 계속 쓰다보면 여러 방법이 잘 떠오르지 않을 수 있다고 생각한다.

 

문제 자체는 그리디의 느낌이라 우선순위 큐로도 풀 수 있을 것 같았다

 

아니 나는 왜 1을 배우면 1만 활용하는 것일까 ? 나도 10을 활용하고 싶은데,, 반복숙달되면 나도 바로 countingSort를 바로 떠올릴 수 있겠지..

 

그래도 merge가 어떻게 동작하는지 알 수 있어서 하나는 얻어 가는 것 같다.

 

leetcode 욕만 했는데 보면 볼수록 지원하는 기능이 많아서 약간 볼매네..