구름톤 챌린지 1주 Day5 - 이진수 정렬

이진수 정렬 (Java)

 

제출한 답 :

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 입력 받기
        String[] nk = br.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);

        String[] numbersStr = br.readLine().split(" ");
        int[] numbers = new int[n];
        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(numbersStr[i]);
        }

        // 정렬
        Sort(numbers);
        // k번째 정수 출력
        System.out.println(numbers[k - 1]);
    }
    // 정렬
    private static void Sort(int[] arr) {
        for(int i = 0; i < arr.length; i++){
            for(int j = i + 1; j < arr.length; j++){
                if(compare(arr[i], arr[j])){
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
    }

    // 비교
    private static boolean compare(int a, int b) {
        int A = count(a);
        int B = count(b);
        if (A != B){
            return A < B; // 1의 개수가 적은 순으로 정렬
        }
        return a < b; // 10진수를 기준으로 오름차순 정렬
    }

    // 1의 개수 계산
    private static int count(int num) {
        int count = 0;
        while (num > 0){
            if (num % 2 == 1){ // 나머지가 1일 때 수 증가
                count++;
            }
            num /= 2;
        }
        return count;
    }

}

 

문제를 풀면 풀수록 아 내 실력이 정말.. 이정도 안되는구나라고 느끼는데 심지어 별 두개짜린데도 이정도 인데;; 

3-4 개는?ㅋㅋㅋㅋ 잘 모르는 상태에서 굳이 문제를 푸는 의미가 있을까 싶지만..그래도 이왕 하기로 한거 해보는데까지...

 

문제 풀이

필요한 개념

• 2진수
• 조건부 정렬

분석

문제에서 주어지는 N개의 정수를 2진수로 변환하고, 변환된 진수의 1의 개수를 가지고 정렬하여 K 번째 숫자를 찾아보는 문제입니다.
단, 문제에서 정렬 조건이 1의 개수 뿐만 아니라, 같다면, 10진수 값으로도 비교하라고 합니다. 즉, 조건의 여러 개 있는 정렬 문제 입니다.

문제 풀이

문제 풀이를 위해서는 2가지를 수행해야 합니다.
1. 정수를 2진수로 바꾸면서, 1의 개수를 Counting 하기
2. 정렬하고 K 번째 수 찾기

2가지 과정을 해결하면, 정답을 찾을 수 있습니다. 정렬을 위해서 Pair 의 개념을 배워볼 것이고, 2진수 변환을 위해서, bitCount(num) 를 배워보려고 합니다.

2진수로 변환하기

자바에서 어떤 정수 num을 2진수로 변환하는 방법은 Integer.bitCount(num) 입니다.

int bits = Integer.bitCount(num);

물론 2진수 가 아니라 N진수로 바꿀 때는 아래의 코드로 바꿀 수 있습니다. 다만, toString 메소드를 사용하기 때문에 정수형으로 변환이 필요하다는 점을 잊으시면 안됩니다.

int decimalNumber = 15;
Strng binaryNumber = Integer.toString(decimalNumber, 2);

이를 입력을 받는 모든 정수에 적용을 하면 다음과 같습니다.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
				// N과 K를 입력받는다.
        int N = sc.nextInt();
        int K = sc.nextInt();
				// 입력되는 정수를 2진수로 변환하고, 1의 개수를 센다.
        for(int i = 0; i < N; ++i) {
            int num = sc.nextInt();
            int bits = Integer.bitCount(num);
        }
    }
}

Pair

자바에서 Pair는 두 개의 값을 저장하는 데 사용되는 클래스입니다. 즉, 두 개의 값을 하나의 단위로 묶어서 사용할 수 있도록 도와줍니다.

ArrayList<Pair>는 자바에서 Pair 객체들을 저장하는 동적 배열을 선언할 수 있습니다. Pair 각각 요소에 접근하기 위해서는 getLeft() 와 getRight() 를 사용해서 접근할 수 있습니다.

ArrayList<Pair> pairs = new ArrayList<>();
pairs.add(new Pair('Java', 100));
for (Pair<String, Integer> pair : pairs) {
      String language = pair.getLeft();
      int year = pair.getRight();
      System.out.println("Language: " + language + ", Year: " + year);
}

Pair 의 개념을 사용해서 한 데이터의 객체를 아래와 같이 묶어줄 수 있습니다.

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
				// Pair을 보관하기 위한 ArrayList
        ArrayList<Pair> pairs = new ArrayList<>();
        for(int i = 0; i < N; ++i) {
            int num = sc.nextInt();
            int bits = Integer.bitCount(num);
						// 2진수 변환시 1의 개수와 10진수를 하나의 Pair로 선언
            pairs.add(new Pair(bits, num));
        }
    }
}

Pair가 필요한 이유는 이 문제가 정렬 문제이면서, 정렬의 우선 순위 조건과 정렬에서 필요한 데이터를 하나의 데이터로 관리해야 합니다.

위 코드에서 중요한 점은 결국에 이 정렬에 있어서 필요한 점은 2진수로 변환했을 때 1의 개수 와 10진수 둘 다 필요한 점을 확인해야 합니다. 이렇듯 정렬 문제에서 정렬의 우선 순위 조건과 정렬에서 필요한 데이터를 하나의 데이터로 관리해야 하기 때문에 Pair 의 개념이 필요합니다.

다중 조건 정렬

Pairs 라는 2진수 변환 시 1의 개수와 10진수를 담고 있는 자료형을 만들었습니다. 이 자료형을 정렬하려고 하는데, 위에서 이야기 한 것처럼 2개의 정렬 조건을 가지고 있습니다.

이렇게 다양한 조건으로 Pair 를 Comparable 인터페이스를 활용해서 비교 가능하게 만들려고 합니다.

• Comparable 인터페이스를 구현하는 것은 클래스가 비교 가능하다는 것을 의미합니다. 즉, Pair 객체들을 비교할 수 있도록 하기 위해 사용됩니다. Comparable 인터페이스는 compareTo() 메소드를 정의하도록 강제하며, 이 메소드를 통해 객체 간의 비교 기준을 정의할 수 있습니다.

즉 위의 인터페이스를 활용해서 비교할 때 우선순위를 만들어줄 수 있습니다. Pair 라는 자료형에 정렬 속성을 부여한다고 생각하면 개념적으로는 간단합니다.

실제로 코드 역시 어떤 클래스에 새로운 메소드를 추가하는 것과 비슷합니다.

1. Comparable 인터페이스를 구현을 만들어 주고, Pair를 선언할 때 입력 받은 값을 Comparable 속성에 할당합니다.
2. 또 다른 Pair o 와 비교합니다. compareTo 는 비교 함수입니다. true와 false를 반환하며 True때는 Pair o 보다 기존의 Pair 크다는 뜻이고, false를 반환하면 작다는 뜻입니다.
   1. 1의 개수가 차이가 난다면 비교할 Pair 와 계산해서 음수라면 false, 양수라면 true를 반환합니다.
   2. 만약에 비트 수가 같다면 10진수 끼리 비교하고, Pair 와 계산해서 음수라면 false, 양수라면 true를 반환합니다.

class Pair implements Comparable<Pair> {
    int bits;
    int num;
    
    public Pair(int bits, int num) {
        this.bits = bits;
        this.num = num;
    }

    public int compareTo(Pair o) {
        if (this.bits == o.bits) {
            return o.num - this.num;
        } else {
            return o.bits - this.bits;
        }
    }
}

위의 비교 함수를 만들었다면, Collections.sort(); 처리하면 쉽게 정렬할 수 있습니다.

//sort(정렬할 데이터)
Collections.sort(pairs);
//데이터 중에서 가장 마지막(큰 데이터) 를 출력한다.
System.out.println(pairs.get(K-1).num);

 

답 :

import java.util.*;

class Pair implements Comparable<Pair> {
    int bits;
    int num;
    
    public Pair(int bits, int num) {
        this.bits = bits;
        this.num = num;
    }

    public int compareTo(Pair o) {
        if (this.bits == o.bits) {
            return o.num - this.num;
        } else {
            return o.bits - this.bits;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        ArrayList<Pair> pairs = new ArrayList<>();

        for(int i = 0; i < N; ++i) {
            int num = sc.nextInt();
            int bits = Integer.bitCount(num);
            pairs.add(new Pair(bits, num));
        }

        Collections.sort(pairs);

        System.out.println(pairs.get(K-1).num);
    }
}