알고리즘 기초 1/2. 301 - 수학 1(연습)
2089번. -2진수

문제

2089번 문제 링크

solution 1

const fs = require("fs");
let input = Number(fs.readFileSync("/dev/stdin").toString().trim());

// input이 0이라면 0을 출력한다.
if(input === 0){
    console.log(0);
} else {
    let remainderArr = [];

    // input을 -2로 나눈 몫이 0이라면
    while(input / -2 !== 0){
        // input을 -2로 나눈 나머지
        let remainder = input % -2;

        if(remainder === 1 || remainder === -1){
            // -13을 -2로 나누면 6.5가 나온다.
            // 이는 10진수 -> 2진수 계산에 사용될 수 없으므로
            // 나머지를 1이나 -1로 만드는 숫자로 바꿔줘야한다.
            // -2 * 7 = -14 -> 나머지 1
            // 즉, 6.5에서 소수점 제거 후 더하기 1 -> 7
            input = Math.floor(input / -2) + 1;

            remainderArr.push(1);
        } else if(remainder === 0){
            input = Math.floor(input / -2);

            remainderArr.push(0);
        } 
    }
    
    console.log(remainderArr.reverse().join(""));
}

solution 2

const fs = require("fs");
let input = Number(fs.readFileSync("/dev/stdin").toString().trim());

if(input === 0){
    console.log(0);
} else {
    let remainderArr = [];

    // input을 -2로 나눈 몫이 0이라면
    while(input / -2 !== 0){
        // input을 -2로 나눈 나머지
        let remainder = input % -2;

        if(remainder === 1 || remainder === -1){
            // -13을 -2로 나누면 6.5가 나온다.
            // 이는 10진수 -> 2진수 계산에 사용될 수 없으므로
            // 나머지를 1이나 -1로 만드는 숫자로 바꿔줘야한다.
            // -2 * 7 = -14 -> 나머지 1
            // 즉, 6.5에서 반올림 처리.
            input = Math.ceil(input / -2);

            remainderArr.push(1);
        } else if(remainder === 0){
            // ceil, floor 아무거나 사용해도 문제없다.
            // 나머지가 0이기 때문에.
            input = Math.ceil(input / -2);

            remainderArr.push(0);
        } 
    }
    
    console.log(remainderArr.reverse().join(""));
}

어떤 정답이든 똑같은 원리가 사용된다. 사용된 메서드가 Math.ceil이냐 Math.floor이냐에 따라 달라질 뿐이다.

예시를 통해 코드를 살펴보자. 필자는 ceil을 사용한 solution 2에 데이터를 넣어보겠다.

입력 데이터 input = -13

첫 번째 반복.
-13 / -2 == 6.5
-13 % -2 == -1

6.5는 10진수 -> 2진수 계산할 때 사용될 수 없다.
나머지가 1 또는 0으로 나와야하기 때문이다.
그렇다면 다음 연산을 위해서는 소수점을 제거해야하는데..Math.ceil을 사용한다.

input = Math.ceil(6.5) == 7
remainder = -1

그런데, -1을 이진수에 넣을 수는 없다.
따라서 1로 전환해서 remainderArr에 넣어준다.

두 번째 반복.
7 / -2 == -3.5
7 % -2 == 1

input = Math.ceil(-3.5) = -3
remainder = 1


...

이런 식으로 반복하다보면 결국 input이 1이나 -1이 되는 순간이 온다.
어떤 쪽이든 상관없이 -2로 나눈 나머지는 1이나 -1이 된다.
또한, 몫은 0.5나 -0.5가 된다.

따라서 input이 ceil에 의해 0으로 바뀌고 다음 반복으로 넘어가지않고 while 종료.

remainder 배열의 뒤에서부터 출력해야하므로 reverse와 join을 사용해 뒤집어서 출력한다.

참고 자료

참고 자료 1