[리트코드] 99클럽 코테 스터디 1일차 TIL + Top K Freqent Element

오늘의 학습 키워드

딕셔너리 정렬, Counter 클래스(Collections 모듈)

 

오늘의 회고

2분기 취업을 목표로 매일 코딩 테스트 풀기를 도전하고 있다.

P인간 타파개는 혼자서는 작심이틀이 분명할 것이기에 항해99에서 습관 만들기 프로그램인 99클럽에 지원하였다.

99클럽은 매일 오늘의 코딩테스트 문제를 제공하고, LMS에 해당 문제를 풀었다는 인증을 함으로써 습관을 만들 수 있도록 도와준다.

 

오늘 1일차에는 아래와 같은 내용을 진행하였다.

1. OT in 디스코드

2. 보너스 문제 제공 (30분간 타임어택)

3. 오늘의 문제 풀이 & TIL (개인이 각자 진행)

 

🌱 오늘의 문제

보너스 문제는 리트 코드(Leet Code)의 347. Top K Freqent Element 문제를 풀었다.

정수 배열 nums가 주어질 때, 정수 배열 내 빈도수가 높은 값 k개를 출력하는 문제이다.

예: nums = [3, 3, 3, 4, 4, 5], k = 2 -> 결과: [3, 4]

 

ㅇ

🌱 나의 시도

나의 접근 방법은 반복문을 돌며 각 항목의 빈도수를 세고, 그 값을 딕셔너리에 저장한다.

위 과정에서 도출한 딕셔너리를 value 값을 기준으로 정렬한 후 key 값을 반환한다.

코드는 아래와 같다.

class Solution(object):
    def topKFrequent(self, nums, k):
        # 1. 항목 등장 횟수 저장할 딕셔너리 정의
        cnt_dict = dict()
        # 2. 반복문을 돌며 항목 등장 횟수 카운팅
        for num in nums:
            if num in cnt_dict:
                cnt_dict[num] += 1
            else:
                cnt_dict[num] = 1
        # 3. 등장 횟수(value) 기준 내림차순 정렬
        cnt_dict = sorted(cnt_dict.items(), key=lambda x: x[1], reverse=True)
        # 4. k개의 키 값만 반환
        return [item[0] for item in cnt_dict[:k]]

 

나는 (1) 빈도수를 세고 / (2) 빈도수(value)를 기준으로 정렬하고 / (3) 인덱스(key)를 반환하는 알고리즘을 구현할 때, 위와 같이 딕셔너리를 활용하는 방법을 주로 사용한다. 그런데 이 때마다 더 효율적이고 직관적으로 코드를 짤 수는 없을까? 하는 의문이 들었다.

 

🌱 새롭게 알게 된 점: collections 모듈의 Counter 클래스

오늘 디스코드에서 다른 수강생분이 공유해주셔서 collections 모듈의 Counter 클래스를 사용하는 방법을 알게 되었다. 이 방법을 통해 코드 수를 줄이고 가독성을 향상시킬 수 있다.

기존의 리스트를 Counter 객체로 만든 후 most_common() 메소드에 k 값을 넣어주면 이미 빈도수가 높은 k개에 대해 (key, value) 튜플 형태의 리스트로 추출이 된다. 마지막으로 key 값 추출해주는 코드만 작성해주면 위 코드와 동일한 결과를 출력할 수 있다.

from collections import Counter

class Solution:
    def topKFrequent(self, nums, k):
        counter = Counter(nums)
        most_commons = counter.most_common(k)
        answer = [i[0] for i in most_commons]
        return answer

 

 

위 두 가지 방식은 "정렬"을 이용한 방법이다. 시간 복잡도를 생각해보자.

1. 배열을 돌면서 숫자를 센다. -> O(N)

2. 배열을 정렬한다 -> O(N log N)

3. 순서대로 k개 선택 -> O(k)

최종적으로 정렬을 이용한 방법의 시간 복잡도는 O(N log N) 이라고 할 수 있다.

파이썬은 다양한 라이브러리를 잘 익혀둬야 코테 실력을 쑥쑥 늘릴 수 있을 것이라고 생각한다.

한 번 본 것으로 만족하지 않고 여러 번 다시 읽어보며, 다른 문제에 대입할 수 있도록 연습해야겠다.

 

🚀 내일 학습할 것

1. 우선순위 큐

항해99에서 자바 클럽장님의 발표를 통해 우선순위 큐로 해당 문제를 풀 수 있다는 것을 알게 되었다. 심지어 우선순위 큐로 풀 경우 O(N log k)로 줄일 수 있다. 내일 개념을 좀 더 구체적으로 정리해보면서 이 문제도 우선순위 큐로 다시 풀어보자.

2. BFS/DFS

BFS/DFS 문제를 잘 풀 수 있도록 개념 정리를 해 보자.

 

 

오늘의 후기

항해99 생각한 것보다 더 알차다!

다른 사람들이랑 코드 공유를 할 수 있으니 내가 잘 풀고 있는지, 다른 구현 방법은 어떤 게 있는지 알 수 있다.

또 일주일에 한 번 디스코드로 온라인 스터디를 진행하니, 문제를 풀다 막히더라도 물어볼 곳이 있다는 게 든든하다.

 

좋은 환경을 구축했으니 또 열심히 해보자! 시작이 반인데 벌써 반이나 왔다~ 화이팅!

 

 

 

귀여운 리차-드