문제 개요
하나의 숫자 N이 주어졌을 때, 그 값을 -2진법(음수 2를 밑으로 하는 진법)으로 표현하는 '0'과 '1'로만 이루어진 문자열을 찾는 것이 목표입니다. 단, 반환되는 문자열은 정확히 "0"인 경우를 제외하고 선행 0(leading zero)을 포함해서는 안 됩니다.
예를 들어 입력이 2라면 출력은 "110"이 됩니다. 이는 (-2)² + (-2)¹ = 4 - 2 = 2이기 때문입니다.
해결 접근 방식
일반적인 진법 변환과 원리는 비슷하지만, 밑(base)이 음수라는 점에서 나머지 처리에 주의해야 합니다. 다음 단계를 따릅니다.
ret을 빈 문자열로 초기화합니다.N이 0이면 "0"을 반환합니다.
N이 0이 아닌 동안 다음 과정을 반복합니다.
rem := N mod (-2)로 나머지를 구합니다.N := N / (-2)로 몫을 갱신합니다.rem이 음수이면 rem에 2를 더하고, N을 1 증가시킵니다.
ret := ret + rem— rem을 문자열로 변환해 뒤에 붙입니다.
문자열 ret을 뒤집습니다.
ret을 반환합니다.
여기서 핵심은 C++의 나눗셈 특성입니다. 피연산자가 음수일 경우 나머지도 음수로 계산될 수 있는데, -2진법에서 각 자리의 값은 반드시 0 또는 1이어야 합니다. 따라서 나머지가 음수로 나오면 2를 더해 보정하고 몫을 1 늘려 균형을 맞추는 것입니다.
예제 코드
다음 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string baseNeg2(int N) {
string ret = "";
if(N == 0) return "0";
while(N){
int rem = N % (-2);
N /= -2;
if(rem < 0) rem += 2, N++;
ret += to_string(rem);
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
cout << (ob.baseNeg2(17));
}
입력
17
출력
10001
입력 17에 대한 결과가 "10001"인 이유는 (-2)⁴ + (-2)⁰ = 16 + 1 = 17이기 때문입니다. 낮은 자리부터 차례로 구한 숫자를 마지막에 뒤집으면 최종 답을 얻을 수 있습니다.