[LeetCode] 347. Top K Frequent Elements

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

Top K Frequent Elements - LeetCode

 

347. Top K Frequent Elements

문제 : 주어진 배열에서 가장 빈번하게 나오는 수를 k개수만큼 int [] 배열 형태로 리턴하는 문제

 

예시 1)

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

예시 2)

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

 

풀이

 

[ 첫 풀이 생각 ]

1. HashMap 형태로 {숫자: 빈번도} 형식으로 저장

2. 빈번도 기준으로 정렬

3. int [] 배열에 k 숫자만큼 key를 저장

4. int [] 배열 출력

 

문제점 :

빈번도 기준으로 정렬했을 때, map은 순서가 없으므로 정렬이 안되니까

일단 iterator를 써서 다 꺼낸 뒤에 value 값을 기준으로 정렬해서 배열에 저장했는데

배열에서 꺼낼때의 값이 key값이 아닌 value 값이 되어버리는 문제가 생긴다.

그래서 아예 key, value 가 모두 있는 상태로 value 기준으로 정렬을 하고 저장을 해야하는데...이 부분에서 막혀서 문제를 풀지 못했다.

Arrays.sort()는 매개변수에 배열값이 들어가야 해서 다른 정렬방식을 적용해봐야겠다.

public class TopKElements347 {

    public static int[] topKFrequent(int[] nums, int k) {
    	if(nums.length==1) {
    		return nums;
    	}

      //해쉬 맵 형태로 {숫자:빈번도} 를 저장
    	//Map은 순서유지되지 않고 Key 중복 안됨
    	HashMap<Integer, Integer> kMap = new HashMap<Integer, Integer>();
    	int frequent = 1;
    	for(int i=0;i<nums.length;i++) {
    		//같은 키 값이 있다면 frequent 증가
    		if(kMap.get(nums[i])!=null) {
    			frequent++;
    		}else {
    			frequent=1;
    		}
    		kMap.put(nums[i], frequent);

    		//확인
    		System.out.println("nums[i]="+nums[i]+", frequent="+frequent);
    	}

    	Iterator<Integer> iter = kMap.keySet().iterator();

    	int [] valueList = new int [kMap.size()];
    	int j=0;

    	while(iter.hasNext()) {
    		int key = iter.next();
    		int value = kMap.get(key);
    		System.out.println("key="+key+", value="+value);

    		//valueList에 value 값 정렬하기
    		valueList[j] = value;
    		Arrays.sort(valueList);
    	}

    	//value 값으로 정렬하면 꺼내도 value라서
    	//key값을 얻어오는 걸 고민해봐야함.
		
    	//k개 만큼만 'key'를 output에 담기
		int [] output = new int [k];

    	return output;
    }
}