LeetCode알고리즘 Top K Frequent Elements

오늘 풀어볼 문제는 347번 문제입니다.
난이도는 중간 난이도이며 62.8%의 성공률을 보입니다.

문제를 살펴보겠습니다.

nums 정수 배열이 주어지고 정수 k가 주어집니다.
가장 빈번하게 나온 요소를 k개 리턴해줍니다.
이는 어떤 순서여도 상관없습니다.

 

주어진 예제를 살펴봅시다.

1번 예제는 이미 정렬되어 있네요.
1은 총 3개, 2는 2개, 3은 1개 있습니다.
k가 2니까 가장 빈번하게 나왔던 1과 2가 리턴됩니다.
2번 예제는 1밖에 포함이 안되어있고 k가 1이니 1이 리턴됩니다.

 

딕셔너리를 활용해서 문제를 풀어보겠습니다.

func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
    var dict = [Int: Int]()
    
    // 횟수 증가
    for i in nums {
        if let value = dict[i] {
            dict.updateValue(value + 1, forKey: i)
        } else {
            dict[i] = 1
        }
    }
    
    // 튜플 저장
    var tuple: Array<(key: Int, value: Int)> = []    
    for (key, value) in dict {
        tuple.append((key,value))
    }
    
    // value기반으로 정렬
    var sorting = tuple.sorted { $0.1 > $1.1 }
    
    // key담을 배열
    var answer = [Int]()    
    for i in 0..<k {
        if !sorting.isEmpty {
            answer.append(sorting.removeFirst().key)
        }
    }
        
    return answer
}

dict 딕셔너리 생성 후 몇 개인지 확인하기 위해 for 루프를 돌면서 1씩 값을 증가해줍니다.
tuple튜플 생성 후 (key, value) 배열을 생성해줍니다.
for 루프를 돌면서 key, value를 넣어줍니다.
value를 기준으로 정렬해줍니다.
k만큼만 리턴하기 때문에 0부터 k-1까지 answer배열에 붙여줍니다.

문제에서 제공해준 예시로는 부족한 느낌 같아서 새로운 예시로 전체적인 FLOW를 그려봤습니다.

그리고 제출!

통과는 했지만 그냥 생각나는 대로 풀어서 그렇게 좋은 방법은 아닌 것 같아요.
우선순위 큐를 사용해봐도 될 것 같네요.

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