[Java] LeetCode 347. Top K Frequent Elements

[Java] LeetCode 347. Top K Frequent Elements

 

문   제 : 

정수 배열 nums[] 와 정수 k가 주어진다. 

nums 배열 안에서 가장 많이 존재하는 값 k개를 반환해라.

 

Constraint

{ 1 <= nums.length <= 10^5 }

{ -10^4 <= nums[i] <= 10^4 }

{ k is in the range [1, the number of unique elements in the array]. }

{ It is guaranteed that the answer is unique. }

 

Matter

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

 

Example )

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

=========================================================================

Input: nums = [1], k = 1
Output: [1]

 

 

---

접   근 : 

사용자 클래스를 하나 만들고, 그 클래스를 정렬해서 반환한다.

---

해    결  &  설    명: 

사용자 클래스 N을 만든다. N 클래스는 멤버변수 number, count를 갖는다. number는 해당 숫자이고, count는 그 숫자가 몇번 나왔는지에 대한 정보이다.

 

그리고 N 객체끼리 정렬이 가능하도록 Comparable을 인터페이스로 구현해준다.정렬 기준은 count의 큰 순서대로 정렬하는것이다. 만약 count가 같다면, number가 작은것이 앞에 오도록한다.

 

nums를 정렬해준다. nums를 순회하면서 만약 지금 값이 이전값과 같다면 count+1를 해주고, 다르다면 list에 새로운 객체 N 을 만들어서 추가해준다.마지막 count된 number는 list에 추가 되지 않기 때문에 반복문이 끝나고 list에 객체 N을 추가해준다.

 

그리고, list를 정렬해준다.

그러면 list는 가장 많이 등장한 숫자로 이루어진 객체를 기준으로 정렬되게 되는데, 그러면 k번 만큼 앞에 있는 list를 참조해서 배열로 집어 넣어주면 된다.

 

---

결   과  :

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Arrays.sort(nums);

        int res[] = new int[k];
        ArrayList<N> list = new ArrayList<>();

        int temp = nums[0];
        int count = 1;
        for(int i=1; i<nums.length; i++){
            if(nums[i] == temp){
                count++;
            }
            else {
                list.add(new N(temp, count));
                temp = nums[i];
                count = 1;
            }
        }
        // 마지막 요소 추가
        list.add(new N(temp, count));

        Collections.sort(list);

        for(int i=0; i<k; i++){
            res[i] = list.get(i).number;
        }

        return res;
        
    }
    public class N implements Comparable<N>{
        public int number;
        public int count;

        public N(int number, int count){
            this.number = number;
            this.count = count;
        }

        public int compareTo(N n1){ // count가 큰 순서대로 정렬
            if(this.count > n1.count) return -1;

            else if(this.count < n1.count) return 1;

            else {
                if(this.number > n1.number) return 1;
                else return -1;
            }
        }
    }
}