[구름톤챌린지] 5일차 이진수정렬

[구름톤챌린지]

문제 # https://level.goorm.io/exam/195687/%EC%9D%B4%EC%A7%84%EC%88%98-%EC%A0%95%EB%A0%AC/quiz/1

 

내가 작성한 코드

import java.io.*;
import java.util.*;

class Pair implements Comparable<Pair>{
	int num, cnt;
	
	Pair(int num, int cnt){
		this.num = num;
		this.cnt = cnt;
	}
	
	@Override
	public int compareTo(Pair p){
		return this.cnt == p.cnt ? p.num - this.num: p.cnt - this.cnt;
	}
}
class Main {
	static int N, K; // 10진수 정수 개수, 찾으려는 정수 위치 
	
	static ArrayList<Pair> nums = new ArrayList<>();
	static PriorityQueue<Pair> pq = new PriorityQueue<>();
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; ++i){
			int num = Integer.parseInt(st.nextToken());
			int cnt = getOneCnt(num);
			// nums.add(new Pair(num,cnt));
			pq.add(new Pair(num, cnt));
		}
		
		// Collections.sort(nums);
		// System.out.println(nums.get(K-1).num);
		for(int i=0; i<K-1; ++i){
			pq.poll();
		}
		System.out.println(pq.peek().num);
	}
	
	static int getOneCnt(int num){
		int cnt = 0;
		while(num > 0){
			cnt += num % 2;
			num /= 2;
		}
		return cnt;
	}
}

 

풀이 및 배운 점

 

처음에는 ArrayList<Pair> 에 모두 저장한 후, 정렬을 하여 K-1 번째 요소의 값을 출력하는 방법으로 문제를 해결하고자 하였다.

제출 결과 25개의 테스트케이스 중 마지막 24, 25번째 테스트케이스에서 시간 초과가 났다.

PriorityQueue에 넣는 방식으로 하였더니 테스트케이스가 모두 통과되어 문제를 해결할 수 있었다.

 

Collections.sort() 의 시간복잡도가 최악일 경우 `O(nlogn)` PriorityQueue의 시간복잡도가 `O(logn)` 이라 이 차이로 인해 통과가 된 것일까?

 

이번에 코드를 작성하면서 Collections.sort() 내부 구현 정렬 알고리즘이 `TimSort`라는 것으로 구현되어 있다는 것을 알게되었다.

 

내일 공개되는 문제 해설을 보면서 어떤 방식으로 푸는 것이 좀 더 효율적인지 배워야겠다.

 

TimSort

삽입정렬과 병합정렬의 조합으로 만들어진 정렬

 

+추가 ( 공개된 해설지)

 

`Integer.bitCount(num)`

2진수로 변환하였을 때, true bit(1) 개수를 반환하는 메소드

 

`Pair`

두 개의 값을 저장하는데 사용하는 클래스. `getLeft()`와 `getRight()` 사용하여 접근 가능

 

해설지에서 처음 내가 풀었던 방식과 동일하게 클래스를 담는 동적 배열을 만들고, Comparable 인터페이스를 구현하여 compareTo를 오버라이딩하였다. 그런데 나는 Integer.bitCount(num)이라는 메소드를 사용하지 않아서 24, 25번 테스트케이스에서 통과하지 못한 것 같다.

 

bitCount()의 내부가 어떻게 되어는지 알고싶어 확인해보니, 이해하기가 어려웠다. 다만 이 코드를 확인하면서 24, 25번 케이스에서 통과하지 못한 원인은, 정수의 크기가 클 때, 2진수에서 1의 개수를 세는 메소드를 사용하는 부분인 것 같다.

@IntrinsicCandidate
    public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }