[Leetcode 아주 상세한 문제풀이] 347. Top K Frequent Elements - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 347번 문제 Top K Frequent Elements 다.

우선 문제를 살펴보자.

 

리트코드 347번 문제 Top K Frequent Elements 링크

https://leetcode.com/problems/top-k-frequent-elements/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:
Input: nums = [1], k = 1
Output: [1]
 
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

 

 

문제 설명

문제를 간략히 살펴보자. 정수로 이루어진 배열 nums와 정수 k가 입력값으로 주어진다. 이때 'k most frequent elements'를 리턴하라는 문제다. 즉, k=2 라면 주어진 배열 중 가장 흔한 정수 2개를 리턴하라는 것이다. 이때 리턴하는 정수들의 순서는 상관이 없다. 예를 들어 문졔 예시 1번에서 처럼 k=2 인 경우, 우리는 주어진 배열에서 가장 흔한 정수 1과 그 다음으로 흔한 정수 2를 순서에 상관 없이 리턴하면 된다. 문제가 매우 간단하기 때문에 설명을 여기서 마치고 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제에 가장 쉽게 접근하는 방법은 파이썬에서 사용되는 built-in 데이터 구조와 라이브러리를 이용하는 것이다.

예를 들어 우리는 주어진 배열의 정수를을 하나씩 dictionary에 넣는 경우를 생각해 볼 수 있다.

이때 각 정수가 몇 개씩 들어가는지 카운트 할 수 있다.

Dictionary에 주어진 모든 정수를 넣은 후 그 개수에 따라 내림차순 정렬을 하게되면,

가장 많은 개수를 가진 정수가 가장 앞에 위치하게 되어 k값에 따라 가장 흔한 정수를 쉽게 찾아낼 수 있다.

다르게 접근하는 방법도 있는데 주어진 배열의 숫자를 하나씩 카운트 하는 것이다.

예를 들어 문제 예시 번에서 주어진 것 처럼 [1, 1, 1, 2, 2, 3]이란 배열을 빈 리스트에 두개 만들어,

하나는 각 숫자를 하나씩 넣어주면서 동시에 다른 리스트에 그 숫자가 몇 개나 들어갔는지 카운트 한다.

이 경우 [1, 2, 3]과 같이 차례로 들어가며 각 숫자의 개수는 [3, 2, 1]과 같이 카운트된다.

위 두 가지 접근 방법으로 이 문제를 풀어보자.

 

 

문제 풀이1

정수 배열 nums과 정수 k를 입력받을 함수를 정의해 준다 (line 1)

그리고 정수를 하나씩 카운트하며 넣어줄 dictionary를 만들어 준다 (line 2)

우리는 주어진 정수 배열 nums의 각 정수를 하나씩 dictionary에 넣어줄 것인데 (line 3)

우리는 숫자 그 자체보다는 그 숫자의 개수를 알아내는 것이 중요하다.

따라서 그 숫자를 index로 하여 dictionary 안에서 각 숫자의 개수를 카운팅한다 (line 5)

여기서 freq_map.get (num, 0)이란 표현은 num에 해당하는 값 (value)을 가져오고 (get)

만약 dictionary에 그 값이 없다면 0을 가져오라는 표현이다.

우리는 freq_map을 통해 특정 숫자의 개수를 카운트 하고 있으므로,

만약 해당 숫자가 이미 존재 한다면 이전까지 카운팅 한 숫자의 개수를 가져오게 된다.

주어진 배열 nums과 그 개수를 dictonary에 key와 value값을 모두 넣은 후,

우리는 개수 순서대로 '내림차순'배열을 할 것이다 (line 8)

이렇게 내림차순 배열을 하게 되면 가장 흔한 값이 가장 처음에 위치하게 된다.

여기서 중요한 파이썬 표현 중 하나는 key=lambda x:x[1]라는 것인데,

dictionary는 key-value 쌍으로 되어 있으므로 x[1] 즉 value 기준으로 정렬을 하라는 것이다.

최종적으로 우리가 리턴하고자 하는 값은 가장 흔하게 존재하는 배열의 정수값 이다.

따라서 정렬된 dictionary의 item (= key-value 페어)에서 key값을 리턴해준다 (line 11)

 

 

문제 풀이 코드1

def topKFrequent(nums, k):
    # Step 1: Create a dictionary to store the frequency of each number
    freq_map = {}
    for num in nums:
        freq_map[num] = freq_map.get(num, 0) + 1
    
    # Step 2: Sort the dictionary items based on their frequency in descending order
    sorted_items = sorted(freq_map.items(), key=lambda x: x[1], reverse=True)
    
    # Step 3: Return the first k keys from the sorted dictionary items
    return [item[0] for item in sorted_items[:k]]
 
# Test cases
print(topKFrequent([1,1,1,2,2,3], 2))  # [1,2]
print(topKFrequent([1], 1))  # [1]
 

 

 

문제 풀이2

이 문제에 접근하는 다른 방식도 있다.

우선 정수 배열 nums과 정수 k를 입력받을 함수를 정의해 준다 (line 1)

그리고 i) 입력받은 정수를 넣어줄 리스트와 ii) 그 개수를 세어줄 리스트를 하나씩 만들어 준다 (line 3-4)

주어진 배열 nums에 존재하는 값들을 하나씩 리스트에 넣어주며 개수를 셀 것인데, (line 6)

해당 값이 리스트에 이미 존재하지 않는다면 그 숫자를 리스트에 넣어주며 카운트를 해주고 (line 10-12)

이미 존재하는 값이라면 그 숫자에 해당하는 인덱스에 해당 하는 값에 1을 더해준다 (line 7-9)

예를 들어 문제 예시 1번에서 처럼 주어진 배열이 [1,1,1,2,2,3]인 경우를 생각해 보자.

우선 처음 1의 경우 배열에 이미 존재하지 않으므로 unique_nums 리스트에 1이 추가되고,

동시에 freqs에 1이 카운팅된다.

그리고 주어진 배열의 두번째 1의 경우 unique_nums 리스트에 이미 존재한다.

따라서 우리는 숫자 1이 unique_nums에서 몇 번째 인덱스에 해당하는지를 확인하고 (line 8)

그 인덱스에 해당하는 freqs 값을 1 더해준다.

이 부분이 살짝 헷갈릴수도 있는데, 우리가 찾고자 하는 것은 각 숫자가 몇개인지 확인해야 하는 것이기 때문에

리스트를 두 개 만들어 하나는 주어진 배열의 숫자를 하나씩 넣어주고 동시에 그 숫자들을 카운팅 하는 것이다.

그 후 bubble sort 방법을 이용하여 숫자 개수 순서대로 정렬을 해준다.

이 부분에 대해서를 자세히 설명된 자료가 많기 때문에 따로 설명하지는 않겠다.

결과적으로 이 과정을 통해 우리는 가장 흔한 숫자 순서대로 내림차순 배열을 할 수 있다.

최종적으로 k만큼의 가장 흔한 숫자를 리턴해준다 (line 23)

 

 

문제 풀이 코드2

def topKFrequent(nums, k):
    # Step 1: Implement a frequency counter using lists
    unique_nums = []
    freqs = []
    
    for num in nums:
        if num in unique_nums:
            index = unique_nums.index(num)
            freqs[index] += 1
        else:
            unique_nums.append(num)
            freqs.append(1)
 
    # Step 2: Implement a sorting algorithm (bubble sort) to sort the numbers based on their frequencies
    n = len(unique_nums)
    for i in range(n):
        for j in range(0, n-i-1):
            if freqs[j] < freqs[j+1]:
                freqs[j], freqs[j+1] = freqs[j+1], freqs[j]
                unique_nums[j], unique_nums[j+1] = unique_nums[j+1], unique_nums[j]
    
    # Step 3: Return the first k numbers with the highest frequencies
    return unique_nums[:k]
 
# Test cases
print(topKFrequent([1,1,1,2,2,3], 2))  # [1,2]
#print(topKFrequent([1], 1))  # [1]
 

 

 

관련 문제

리트코드 23번 Merge K sorted lists 문제풀이

 

 

347. Top K Frequent Elements