[코드트리] 십진수와 이진수 - 자바(Java)

문제

https://www.codetree.ai/problems/decimal-and-binary-number?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

코드

첫 번째 줄에 이진수 N을 입력받아 십진수로 변환한 값에 17을 곱한 후 다시 이진수로 변환하여 출력하는 문제다.

• N은 최대 1000 자릿수까지 공백 없이 주어진다.

큰 숫자의 연산이 필요할 때 사용하는 BigInteger를 통해 쉽게 구현할 수 있다.

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();

        BigInteger decimal = new BigInteger(n, 2); // 10진수로 변환
        BigInteger binary = decimal.multiply(BigInteger.valueOf(17)); // 17 곱하기

        System.out.println(binary.toString(2)); // 2진수로 변환하여 출력
    }
}

 

위와 같이 BigInteger를 활용해 쉽게 문제를 해결하였지만 문제가 의도한 대로 푼 것 같지 않은 찝찝함이 남아 있었다.

곰곰이 생각해 보니 2진수의 값을 왼쪽으로 shift 할 때마다 2배씩 증가한다는 사실을 깨달았다. 이로써 직접 구현하여 풀 수 있었다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String n = sc.next();
        // 왼쪽으로 4번 shift(16배)
        String shift = n + "0000";
        // 자리수 맞추기
        n = "0000" + n;

        // carry 연산을 위한 변수
        int carry = 0;
        // 결과를 담을 StringBuilder
        StringBuilder result = new StringBuilder();

        // n 역순으로 반복
        for (int i = n.length() - 1; i >= 0; i--) {
            int a = n.charAt(i) - '0';
            int b = shift.charAt(i) - '0';
            int sum = a + b + carry;

            // 이진수 계산
            if (sum % 2 == 0) {
                result.insert(0, "0");
            } else {
                result.insert(0, "1");
            }

            // carry 연산
            if (sum >= 2) {
                carry = 1;
            } else {
                carry = 0;
            }
        }

        // carry가 남아있으면 "1" 붙임
        if (carry == 1) {
            result.insert(0, "1");
        }

        System.out.println(result);
    }
}

• 2진수의 shift 연산과 덧셈 시 발생하는 carry 연산에 대해서 이해하면 풀기 쉽다.
• 2진수의 특성상 왼쪽으로 이동할 때마다 2배씩 증가한다. (타입의 범위로 인해 항상 그런 것만은 아님)
  • 입력받은 n 문자열 뒤에 "0000"(왼쪽으로 4번 shift)을 붙여줌으로써 16배가 된다.
• n에 "0000"을 더한 문자열 shift와 입력받은 문자열 n을 더하면 정확히 17배가 된다. 반복문 인덱스를 맞추기 위해 n에 문자열  "0000"을 더한다.
• 반복문을 통해 n과 shift 문자열의 각 자릿수와 캐리 연산을 위한 carry 변수를 더한다.
• 더한 값을 2로 나눈 나머지가 1이면 "1", 0이면 "0"을 StringBuilder의 첫 번째 인덱스에 추가한다.
• 더한 값이 2 이상인 경우 carry를 1, 아닌 경우 0으로 변경한 뒤 위 연산을 반복한다.
• 마지막에 carry가 남아있으면 "1"을 첫 번째 인덱스에 추가한 후 이를 출력한다.