[릿코드] Reduce Array Size To The Half

문제

릿코드 1338. Reduce Array Size To The Half

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

 

코드

class Solution(object):
    def minSetSize(self, arr):
        answer = 0
        
        count_num = {}
        for num in arr:
            if num not in count_num.keys():
                count_num[num] = 1
            else:
                count_num[num] += 1

        values = sorted(list(count_num.values()))

        while sum(values) >= len(arr)//2:
            values.pop()
            answer += 1

        return answer

 

풀이

answer = 0
        
count_num = {}
for num in arr:
    if num not in count_num.keys():
        count_num[num] = 1
    else:
        count_num[num] += 1

answer은 최종적으로 반환할 변수로써, 절반 이상을 제거하기 위해 필요한 최소한의 정수 집합 크기를 담을 변수이다. 

 

count_num은 arr 배열 안에 각 숫자들이 몇개 나왔는지에 대한 정보를 담을 해시다.

for문을 통해 arr의 원소들 각각을 돌면서

count_num 해시에 해당 원소를 센 적 없다면 count_num[해당원소]의 밸류 값을 1 로 초기화하고,

해당 원소를 센 적 있다면 count_num[해당원소]의 밸류값을 1 늘린다.

 

values = sorted(list(count_num.values()))

빈도수 리스트를 오름차순으로 정렬한다.

오름차순으로 정렬하는 이유는 배열의 마지막 원소부터 가장 자주 나오는 수를 차례로 pop()할것이기 때문이다. 

 

while sum(values) >= len(arr)//2:
    values.pop()
    answer += 1

빈도수 배열 원소들의 합이 원래 주어진 arr의 원소 갯수의 절반 밑으로 내려가면 다음의 작업을 중단한다.

가장 큰 빈도수 부터 차례로 pop하고, pop할때마다 answer을 1 늘린다.

 

 

다른 코드

같은 스터디원이신 지형님의 코드이다.

https://hanghae99-python.notion.site/1338-Reduce-Array-Size-to-The-Half-e996488a59a94397a0988c2c989e6ff9?pvs=4

from collections import Counter
class Solution:
    def minSetSize(self, arr: [int]) -> int:
        count_list = Counter(arr).most_common()
        total = 0
        count = 0

        for _, list_count in count_list:
            total += list_count
            count += 1

            if total >= len(arr) // 2:
                return count

 

 

풀이

전 코드와 비슷한 흐름이지만, 이 코드에선 파이썬의 Counter클래스와 most_common함수를 활용하였다.

count_list = Counter(arr).most_common()

Counter모듈을 이용하여 각 원소들이 몇번 나왔는지에 대한 객체를 만들고, 

most_common()을 이용해서 가장 많이 나온 빈도수 차례로 정렬한다.

ex) arr = [3, 3, 3, 5, 5, 3, 5, 2, 2, 7] 이라면, count_list = [(3, 4), (5, 3), (2, 2), (7, 1)] 이다.

 

for _, list_count in count_list:
    total += list_count
    count += 1

    if total >= len(arr) // 2:
        return count

count_list의 각각의 아이템들을 차례로 total에 더함과 동시에 count의 숫자도 1 늘려준다.

만약 total이 주어진 숫자의 원소 갯수의 절반 이상이 되면

count를 반환하고 함수는 종료된다.

 

새롭게 배운점 / 느낀점

• Counter 클래스
  • collection 모듈의 Counter 클래스는 배열을 인자로 받아서 각 원소가 몇번씩 나오는지 저장된 딕셔너리 형태의 객체를 얻게된다.
  • 시간복잡도는 O(n) 이다.
• most_common() 함수
  • 원소의 개수가 많은 순으로 정렬된 배열을 리턴한다.

• 여탯동안 해시를 이용해서 원소의 개수들을 알아봤었는데, counter 클래스를 알게 되었다. 시간복잡도도 해시와 같으니 앞으로는 원소의 빈도를 세아릴때 Counter클래스와, 최빈도값순으로 나열할 시 most_common() 함수도 사용하면 좋을것 같다.

 

다른 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)