24-06-16 알고리즘 문제 풀이

오늘은 여태까지 진행되었던 프로젝트 내용을 정리하면서 주로 시간을 보냈던 것 같다. 여태까지 진행했던 내용들을 한 번 쫙 정리하니 도움이 어느정도 되었던 것 같다.

 

여기에는 오늘 풀어본 알고리즘 문제 풀이를 하나 정리해본다.

 

1. 알고리즘 문제 풀이

오늘은 leetcode에 있는 '347. Top K Frequent Elements' 문제를 풀어보았다.

1-1. 풀어본 문제

[문제]

 

정수 배열 nums와 정수 k가 주어졌을 때, 배열에서 가장 빈번한 요소 k개를 반환하세요. 순서는 상관 없습니다.

 

- 예시 1

입력: nums = [1,1,1,2,2,3], k = 2

출력: [1,2]

 

- 예시 2

입력: nums = [1], k = 1

출력: [1]

 

 

- 제한 사항

• $1 {\;}{\leq}{\;} nums.length {\;}{\leq}{\;} 10^{5} $
• $-10^{4} {\;}{\leq}{\;} nums[i] {\;}{\leq}{\;} 10^{4} $
• k는 [1, 배열의 서로 다른 요소의 갯수] 사이에 있습니다
• 답의 유일함이 보장됩니다

알고리즘의 시간 복잡도는 O($n{\log}n$)보다 더 나아야하며, 여기서 n은 배열의 크기 입니다.

 

1-2. 문제 풀이

문제를 작은 부분 여러개로 나누어 생각해보았더니 생각보다 쉽게 풀 수 있었다.

 

먼저 배열에 들어있는 숫자들의 개수부터 세야했다. Map을 이용하여 어렵지 않게 해결할 수 있었다. 그러고 난 뒤 고민을 조금 했었는데 LinkedHashMap 같은 것을 이용해서 Map을 정렬해볼까도 생각을 했었는데 별로 좋은 방법이 아닌 것 같아서 그것은 보류하고 우선순위큐를 이용해보기로 했다.

 

Map에 들어있는 것을 Pair로 우선순위 큐에 담은 뒤 우선순위 큐에서 k개 만큼 추출하는 방식으로 코드를 작성했다.

 

아래 코드만 보더라도 쉽게 과정을 따라갈 수 있기 때문에 따로 더 설명을 적지는 않아도 될 것 같다.

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        val map: MutableMap<Int, Int> = mutableMapOf()

        // map을 이용해 정수의 갯수 세기
        for (n in nums) {
            map[n] = map.getOrDefault(n, 0) + 1
        }

        // Pair를 요소로 가지는 우선순위큐 만들기
        // 정렬 기준은 Pair의 두 번째 요소(정수의 갯수)
        val priorityQueue = PriorityQueue<Pair<Int,Int>> { a, b -> b.second - a.second }

        // 키와 값을 Pair로 우선순위큐에 담기
        for (key in map.keys) {
            priorityQueue.add(key to map[key]!!)
        }

        // k개 만큼 우선순위큐에서 추출
        val answer = IntArray(k)
        for (i in 0..<k) {
            answer[i] = priorityQueue.poll().first
        }

        return answer
    }
}

위와 같이 코드를 작성했더니 답안으로 잘 통과되었다.

 

이제 이런 문제는 구현하는 것 자체는 크게 어려움이 없는데 어떤게 더 효율적인 방법일지 어떤 자료구조를 사용해야할지 고민이 많이 되는 것 같다. 앞으로도 계속 어떤 상황에 어떤 자료구조가 유리한지 잘 생각하면서 문제를 풀어봐야겠다.

 

2. 오늘 배운 것

- 이전에는 바쁘게 프로젝트 마감하느라 정신이 없었던 것 같은데, 차분히 하나하나 정리할 수 있는 시간이 있어서 좋았다. 마감을 잘 지키는 것 역시 중요한 것 같다. 일정 관리에도 항상 잘 신경써야할 것 같다.