[Algorithm / Java] 백준 10829번 이진수변환

key word : 이진수변환, binary, 십진수

문제

문제는 정말 쉽다. 십진수를 입력하면 이진수로 변환하여 출력해주면 되는 문제이다.

아이디어

이전에 비슷하게 십진수를 이진수로 변환하는 로직을 구현한 적이 있는데 당시에는 이진수의 자릿수가 주어졌었고, 0으로 시작하는 경우까지 고려해야했기 때문에 2의 N제곱승부터 시작해서 for문을 돌며 한 자리씩 채워나갔었다.

이 문제의 경우는 0으로 시작해서는 안되고, 자연수 N의 범위가 1 ≤ N ≤ 100,000,000,000,000라 2의 몇 제곱승인지 잘 감도 안오기때문에 반복문을 사용한다면 for문 보다는 N을 2로 계속 나누며 1이 되는 순간을 체크하는 while문을 사용하는 게 좋을 것 같다.

하지만 최근 재귀를 공부하고 있기 때문에 굳이굳이 재귀함수를 만들어서 풀어보려고 한다. 재귀를 사용해도 반복문을 사용할 때와 구현 방식은 크게 다르지 않다. 계속해서 2로 나누어주며 그 나머지를 챙기는 것이다. 물론 반복문으로 쉽게 구할 수 있는 문제를 굳이 함수를 계속 호출하는 방식으로 푸는 것은 꽤나 비효율적일 것 같다.

++ 궁금해서 while문으로도 풀어서 제출해봤다.

예상 외로 메모리도 시간도 상당히 비슷했다. 재귀가 반복문보다 당연히 오래 걸리고 메모리도 더 쓸 것이라고 생각했는데,, 이유는 좀 더 찾아봐야겠다.

구현

로직 자체는 매우 쉬우니 바로 구현해봤다.

이러한 생각을 바탕으로 자바를 이용해 구현한 결과이다.

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

public class Binary {

	static long N;
	static StringBuilder sb = new StringBuilder();

	public static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Long.parseLong(br.readLine());
	}

	public static void recursion(long n) {
		if(n == 1) {
			sb.append(1);
			return;
		}

		recursion(n / 2);
		sb.append(n % 2);
		return;
	}

	public static void main(String[] args) throws IOException {
		init();
		recursion(N);

		System.out.println(sb.reverse());
	}

}

오류

1. int overflow

   자신만만하게 제출했는데 NumberFormatException이 떠서 당황했다. 쉬워 보여서 문제도 제대로 안 읽고 구현을 시작했던게 실수였다. N의 범위가 int를 가볍게 넘는데 int로 구현한 것이다.. long으로 바꿔주니 문제없이 잘 돌아갔다.

   지난 번과 같은 실수를 반복해서인지 좀 더 반성하게 된다.