[백준 10829번] 이진수 변환 (JAVA)

BOJ - [10829] 이진수 변환

---

🖍 주어진 10진수를 2진수로 변환하여 출력하는 문제
(link) 10829 이진수 변환

---

[풀이 과정]

테스트 케이스 N의 최대값이 10조나 되는 문제다. 때문에 int타입으로 받으면 안되고, long 타입으로 입력을 받으면 된다.

 

--참고--
int타입의 범위 : -2,147,483,648 ~ 2,147,483,647(약 21억)
long타입의 범위 : -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807(약 922경)

 

아무튼 2진수로 변환하는 문제는 재귀로 구현가능하다.

재귀 구현에 대하여 간단하게 설명하자면, 반환 값으로 메소드 자신을 호출하여 반복하게끔 하는 것이다.

때문에 무한 반복을 막기 위한 종료 조건이 꼭 필요하다.

2로 나누고 그 나머지를 사용하면 매우 간단하게 2진수를 구할 수 있다는 사실은 대부분이 알 것이다. (위 그림 참고)
나눗셈과 그 나머지 값을 가져오는 일을 반복적으로 하기 때문에 재귀로 구현할 수 있다. (물론 반복문으로도 가능하다)

 

재귀 함수 내에서 그대로 출력하게 되면 2진수가 반대로 나오기 때문에 StringBuilder에 숫자를 하나씩 저장한 후 거꾸로 출력하게 하는 방법을 사용했다.

 

우선 재귀 종료 조건은 재귀로 호출되는 메소드의 인자(이하 n)가 1이 되었을 때이다. 
1이 되면 더 이상 2로 나눌 수 없기 때문에 반복을 종료해야 한다.

반환 값은 어짜피 StringBuilder에 값을 저장하는 형태이므로 무슨 숫자가 들어와도 상관없지만 .. 일단 1을 반환하겠다.

 

종료 조건을 만족하지 않는 경우, n%2 값을 StringBuilder에 넣어준 후 반환 값으로 메소드를 호출한다. 여기서 인자로 n/2를 넣어준다. 2씩 나눠주면 그 나머지 값이 이진수의 한 자리 숫자가 되기 때문에 n이 반씩 줄어들면서 해당 메소드를 반복하게끔 만드는 것이다.

사실 재귀는 직접 어떻게 돌아가는지 그려보는게 이해가 쉽다.

다음 문제도 재귀를 사용하므로 다음 포스팅에 한 번 올려보겠다.

---

[Pseudocode]

int BinaryTrans(int n)
1. if(n==1) // 종료 조건
    2. 1 저장
    3. return 1
2. else
    3. n%2 저장
    4. return BinaryTrans(n/2)

(재귀 함수 의사 코드)

---

[Code]

import java.util.*;

/**
 * 백준 10829번
 * 이진수 변환
 * 분류 : 수학, 구현, 재귀
 */
public class Problem9 {
    static StringBuilder sb = new StringBuilder(); // 이진수 저장
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        long N = input.nextLong(); // 테스트 케이스의 최대값이 100,000,000,000,000 이므로 long 타입 선언

        BinaryTrans(N);
        System.out.println(sb.reverse().toString()); // StringBuilder에 거꾸로 저장되므로 reverse

        input.close();
    }
    /**
     * 재귀를 통해 주어진 정수 n을 이진수로 변환하여 StringBuilder에 저장한다
     * @param n
     */
    public static int BinaryTrans(long n) {
        if(n == 1) { // 종료조건
            sb.append(1);
            return 1;
        }
        else {
            sb.append(n%2);
            return BinaryTrans(n/2);
        }
    }
}

---

[Result]

---

(2021.07.20 풀이분)

InputMismatch 에러는 입력 테스트 케이스로 들어오는 숫자가 int의 범위를 넘어서 생긴 오류이다.

앞서 말했지만, long으로 입력을 받아줘야함