[자바] 백준 10829 - 이진수 변환 (java)

 문제 : boj10829

---

 

필요 알고리즘 개념

• 이진수
  • 이진수가 무엇인지 알아야 풀 수 있다.
• int보다 큰 수
  
  • int형으로 표현할 수 없는 수를 다룰 수 있어야 한다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  우선 N이 int 표현 범위를 넘어간다. long 범위 이내로는 들어오므로 long으로 받아주면 된다.

 

  자바에 이미 int나 long을 이진수 String으로 변환하는 함수가 있다. 해당 함수를 사용해주면 단순하게 아래의 코드로 이진수 문자열로 출력해줄 수 있다. 0으로 시작하면 안되는 부분도 물론 해당 함수에 포함되어 있다.

Long.toBinaryString(N);

 

---

 

  하지만 저렇게 함수를 바로 써서 출력해주는건 재미없으니 직접 한번 구현해보자. 100,000,000,000,000은 2^49과 2^50의 사이의 값이다(2^50이 1,125,899,906,842,624 이다.). 따라서 N에 대해 우측에서 50번째 bit 까지만 확인해주면 문제에서 제시된 입력값의 최대치까지 모두 확인 가능하다(우측에서 1번째 비트가 2^0에 해당한다. 우측에서 50번째가 2^49에 해당한다.).

 

  그럼 1<<49는 뭘 의미할까? 2^49을 의미한다. (1은 2진수로 000000...001이고, 그걸 비트단위로 전부 왼쪽으로 보내는걸 의미하며 알다시피 그건 2를 곱하는걸 뜻한다. 즉 a<<1은 a*2와 동일하고, a<<49는 a*2^49와 동일하다.)

이 때 주의점은 long으로 사용해야 하므로 1<<49가 아니라 1l<<49 로 해야 한다(1l은 long형 1을 뜻한다.).

그럼 '(n&1l<<i) != 0' 은 뭘 뜻할까? 비트 1을 좌측으로 49번 보낸것과 n과의 비트단위(bitwise) AND 연산이므로, n의 우측에서부터 50번째 bit가 1이였다면 0이 아닌 값이 뜰 것이고, 0이었다면 0이 뜰 것이다. 즉, n의 우측에서 50번째 bit가 1인지 0인지 판단하는 것이다.

 

  위의 과정으로 n의 특정 bit가 1인지 0인지 확인 가능하다. 그렇다면 i를 49부터 0까지 줄이면서 n의 우측에서부터 50번째 bit부터 1번째 bit까지 모든 bit가 1인지 0인지 판단 가능하다. 그럼 이진수로 변경해서 출력을 해줄 수 있다. 주의점은 0으로 시작하면 안된다는 조건이 있으므로, 처음으로 1이 나오는 지점을 체크해서 해당 지점부터 출력을 해줘야 한다. 코드에서는 firstOneChk 변수가 그 역할을 한다.

 

---

 

코드(자바 함수 사용) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println(Long.toBinaryString(Long.parseLong(br.readLine())));
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

코드(직접 이진수로 변환) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long n = Long.parseLong(br.readLine());
        boolean firstOneChk = false;
        StringBuilder answer = new StringBuilder();
        for (int i = 49; i >= 0; i--) {
            boolean is1bit = (n&1l<<i) != 0;
            if (!firstOneChk && !is1bit) continue;
            firstOneChk = true;
            answer.append(is1bit?1:0);
        }
        System.out.println(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}