[구름톤 챌린지, Java] 5일차, 이진수 정렬(구현, 정렬)

문제 링크

구름LEVEL

---

접근 방법

이 문제에 핵심

1. N개의 10진수의 수가 주어집니다.

2. N개의 수를 정렬할 때에는 2진수에서 1의 개수가 많은 순으로 내림차순이며, 같으면 10진수 내림차순으로 정렬됩니다.

3. 정렬된 후 K번째의 수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 조건에 맞게 N개의 수에 대해서 정렬을 진행합니다.

 

3. 정렬이 진행한 뒤 K번째 값을 결과로 출력합니다.

 

 

구현

 

N개의 수를 List<>에 저장합니다.

 

조건에 맞게 Comparator를 만들어서 정렬을 진행합니다.

 

정렬 조건

 

2진수의 1의 개수 내림차순 정렬

 

만약, 같으면?

 

10진수 내림차순 정렬

 

How?

 

2진수의 1의 개수를 구하는 방법

 

저는 Integer.bitCount()를 사용하였습니다.

 

비트의 값은 2진수의 형태이기 때문에 문제에서 주어진 조건과 동일합니다.

 

그래서 저는 Integer.bitCount()를 사용하여 1의 개수를 구한 뒤 정렬을 진행하였습니다.

 

 

예제입력 1.

1. 입력된 정보를 저장합니다.

 

N : 8

 

K : 6

 

Num

1

2

3

4

5

6

7

8

 

2. 조건에 맞게 N개의 수에 대해서 정렬을 진행합니다.

 

Num	1	2	3	4	5	6	7	8
Binary	001(1)	010(1)	011(2)	100(1)	101(2)	110(2)	111(3)	1000(1)

 

정렬 진행!

 

Num	7	6	5	3	8	4	2	1
Binary	111(3)	110(2)	101(2)	011(2)	1000(1)	100(1)	010(1)	001(1)

 

1의 개수 3개 : 7

1의 개수 2개 : 6 5 3 (10진수 내림차순)

1의 개수 1개 : 8 4 2 1(10진수 내림차순)

 

3. 정렬이 진행한 뒤 K번째 값을 결과로 출력합니다.

 

Num	7	6	5	3	8	4	2	1
Binary	111(3)	110(2)	101(2)	011(2)	1000(1)	100(1)	010(1)	001(1)

 

 

6번째 값 4을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 입력값들을 띄어쓰기 기준 나눕니다.
• N개의 개수 조건에 맞게 정렬을 진행합니다.
• 정렬을 진행할 때 2진수 1의 개수를 Integer.bitCount()을 사용하였습니다.
• 정렬 후 N번째 값을 결과로 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

 

결과코드

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws Exception {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //N과 K 입력값 저장
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine(), " ");
        List<Integer> nums = new ArrayList<>();
        //N개의 수 저장
        for(int i=0;i<N;i++){
            nums.add(Integer.parseInt(st.nextToken()));
        }
        //문제 조건에 맞는 정렬 진행
        Collections.sort(nums, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                //2진수 1의 개수 구하기
                int binaryO1Cnt = Integer.bitCount(o1);
                int binaryO2Cnt = Integer.bitCount(o2);
                //1의 개수가 같을 때, 10진수 내림차순 정렬
                if(binaryO1Cnt == binaryO2Cnt){
                    return o2 - o1;
                }else{
                    //1의 개수가 다를 때, 1의 개수 내림차순 정렬
                    return binaryO2Cnt - binaryO1Cnt;
                }
            }
        });
        //정렬된 K번째 값 BufferedWriter 저장
        bw.write(String.valueOf(nums.get(K-1)));
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}

 

---

느낀 점

 

이 문제는 2진수를 구하는 방법을 통해서 1의 개수를 구할 수도 있지만, Integer.bitCount()를 통해서 코드가 훨씬 간결하게 보여지게 되었습니다.

 

여러가지 Method를 아는것도 생각보다 중요하다는 것을 깨닫게 되었습니다.