[백준 02089] -2진수 [Java]

문제

http://boj.ma/2089

요약

• 주어진 10진수를 -2진수로 변환하자.

---

풀이 과정

아이디어

기수가 -2이기 때문에 자릿값이 양수와 음수가 번갈아가며 나온다.

따라서 10진수 N을 -2로 나누었을 때 나머지가 음수라면 아래와 같이 2를 더하고 몫을 1 증가시켜 보정해야 한다.

$N < 0, N = -2q +r = -q + r + 2$

이를 구현하면 다음과 같다.

while (N != 0) {
    int r = N % (-2);
    N /= -2;
    if (r < 0) {
        r += 2;
        N += 1;
    }
    sb.append(r);
}
return sb.reverse().toString();

Java에는 Math.floorMod와 Math.floorDiv를 사용해 나머지가 음수인 경우를 자동으로 보정할 수 있다.

private static String solve(int N) {
    if (N == 0) return "0";
    StringBuilder sb = new StringBuilder();
    while (N != 0) {
        int r = Math.floorMod(N, -2);
        sb.append(r > 0 ? '1' : '0');
        N = Math.floorDiv(N, -2) + (r > 0 ? 1 : 0);
    }
    return sb.reverse().toString();
}

성능 분석

• 시간 복잡도: $O(log |N|)$
• 제출결과: Accepted / 100ms / 14248KB

---

회고

10진수를 기수(base)로 나눈 나머지들을 뒤집으면 해당 기수로 표현한 값을 얻을 수 있다는 사실은 알고 있었지만, 기수가 음수인 경우는 처음 접하는 개념이라 처음부터 풀이를 떠올리기는 쉽지 않았다.

특히 나눗셈 과정에서 나머지가 음수가 될 수 있다는 점이 직관과 맞지 않아 혼란을 느꼈고, 이러한 나머지를 어떻게 자릿값으로 해석해야 할지 고민하게 되었다.

문제를 분석하면서 음수 나머지 역시 다른 자릿수를 통해 양수로 표현할 수 있을 것이라 추측했고, 몫과 나머지를 적절히 조정하면 동일한 값을 유지하면서 유효한 자릿값을 만들 수 있다는 것을 이해하게 되었다.

진법 변환 문제를 많이 풀어보지 않은 상태에서 시작해 처음에는 당황했지만, 이번 문제를 통해 진수와 기수의 의미를 다시 한 번 차분히 생각해보는 계기가 되었다.

---

참고

문제

http://boj.ma/2089

2089번: -2진수

 

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/02089.java

problem-solving/baekjoon-online-judge/easy/02089.java at main · rogi-rogi/problem-solving