[구름톤 챌린지] Day5. 이진수 정렬

구름LEVEL

 

문제 설명

N개의 10진수 정수가 주어진다. 이를 아래의 기준에 따라 정렬하기로 한다.

1. 10진수 정수를 2진수로 나타냈을 때, 2진수에 포함된 1의 개수를 기준으로 내림차순 정렬한다.
2. 1의 개수가 같다면, 원래 10진수를 기준으로 내림차순 정렬한다.

플레이어가 정수를 잘 정렬했을 때, 앞에서 K번째에 위치한 수는 어떤 수가 될지 구해보자.

 

입력

첫째 줄에 주어지는 정수의 수 N과 플레이어가 찾으려는 정수의 위차 K가 공백을 두고 주어진다.

둘째 줄에는 a1, a2,... 이 공백을 두고 주어진다.

8 6
1 2 3 4 5 6 7 8

---

풀이과정

1. 2차원배열을 만들어 num[i][0]에는 주어진 10진수를 넣고, num [i][1]에는 2진수로 만들었을 때의 1의 개수를 저장합니다.

int[][] num = new int[n][2];
s = br.readLine().split(" ");
for(int i=0;i<n;i++){
	num[i][0]=Integer.parseInt(s[i]);
    
    int number = num[i][0];
    while(number>1){//2진수만들기
    	num[i][1]+=number%2;//2진수를 만들면서 1 개수 count
        number/=2;
    }
    num[i][1]+=1;
}

 

2. 만든 2차원 배열을 주어진 조건에  따라 정렬합니다.

2가지 조건 이상으로 정렬을 하기 위해서는 Comparator을 사용해 정렬합니다.

Arrays.sort(num, new Comparator<int[]>(){
	public int compare(int[] a, int[] b){
    	if(a[1]!=b[1]) return b[1]-a[1];
        else return b[0]-a[0];
    }
});

  

3. 정렬된 수들 중에서 k번째 수를 반환합니다.

---

전체 코드

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		int k = Integer.parseInt(s[1]);
		
		int[][] num = new int[n][2];//주어진 수:[0] / 2진수 1개수:[1]
		s = br.readLine().split(" ");
		for(int i=0;i<n;i++){
			num[i][0]=Integer.parseInt(s[i]);
			
			int number = num[i][0];
			while(number>1){
				num[i][1]+=number%2;
				number/=2;
			}
			num[i][1]+=1;
		}
		//2진수에서 1의 개수 내림차순, 10진수 내림차순으로 정렬
		Arrays.sort(num, new Comparator<int[]>(){
			public int compare(int[] a, int[] b){
				if(a[1]!=b[1]) return b[1]-a[1];
				else return b[0]-a[0];
			} 
		});
		
		System.out.println(num[k-1][0]);//k번째 수 출력
	}
}

---

문제 후기

 

확실히 뒤에 이틀은 문제 난이도가 ★★여서 그런지 확실히 바로 풀지는 못하고 조금 생각한 뒤에 푸는 문제들이었습니다.

특히 다음날 정답을 확인하면 제가 푼 방식과 다르게 훨씬 더 쉬운 방법으로 풀 수 있는 풀이가 많아서 많이 배울 수 있었습니다.

특히 2진수에서 1을 세는 방법을 저는 while문을 사용해서 하나하나 다 세어주었지만 

bitCount를 활용해 한줄로 처리할 수 있다는 것을 배울 수 있어서 좋은 문제였다고 생각합니다.

 

다들 구름톤 챌린지 파이팅 해서 매일매일 성장하자고요!!~!