[LeetCode] 347번 문제를 풀어보았다. (ft. java)

2022년 04월 09일 토요일 - 탕수육 마시따

오늘 올려볼 문제는 347번 Top K Frequent Elements 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

n으로 풀려니깐 어렵네요

입력

사진에서도 볼 수 있듯이 int 배열 1개와 int 값 1개가 입력으로 들어온다.

---

풀이 및 코드

배열의 원소들 중에서 빈도수가 높은 것들 k개를 배열에 담아서 리턴하는 문제다.

오늘은 처음부터 정답을 생각해냈지만 n으로 풀기위해서 고민을 좀 했다.

쉽게 푸는 방식은 priority queue를 사용하여 푸는 방식이다.

n으로 풀기 위해서는 hashmap을 이용하여 원소의 빈도값을 저장하고 arraylist를 만들어 해당 빈도값에 해당하는 원소들을 모두 저장해놓는다.

그리고 빈도수가 높은 수부터 k개 만큼 뽑는 방식으로 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer>[] arr = new ArrayList[nums.length + 1];

        for(int num : nums)
        {
            map.put(num, map.getOrDefault(num, 0) + 1);

            if(arr[map.get(num)] == null) arr[map.get(num)] = new ArrayList<Integer>();

            arr[map.get(num)].add(num);
        }

        int[] result = new int[k];
        int index = 0;

        Loop:
        for(int i = nums.length; i >= 0; i--)
        {
            if(arr[i] == null) continue;

            for(int j = 0; j < arr[i].size(); j++)
            {
                if(map.containsKey(arr[i].get(j)))
                {
                    map.remove(arr[i].get(j));
                    result[index++] = arr[i].get(j);
                }

                if(index == k) break Loop;
            }
        }

        return result;
    }
}

---

제출 화면

오늘은 n으로 풀려고해서 코드가 좀 복잡해졌다.

내일도 재밌는 문제가 나왔으면 좋겠다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.