C++를 활용한 숫자 인코딩 알고리즘 완벽 가이드

음이 아닌 정수 n이 주어졌을 때, 이 숫자를 특정 규칙에 따라 인코딩된 형태로 변환하는 문제를 살펴보겠습니다. 인코딩 규칙은 다음 표와 같습니다.

표에서 확인할 수 있듯이, 각 숫자는 해당 범위 내에서 이진수처럼 순차적으로 증가하며, 자릿수가 늘어날 때마다 앞자리가 초기화되는 패턴을 보입니다. 예를 들어 숫자가 23이라면 결과는 "1000"이 되고, 54라면 "10111"이 됩니다.

문제 해결 접근 방법

이 문제는 로그 연산과 이진수 변환을 조합하면 효율적으로 해결할 수 있습니다. 해결 과정은 다음과 같습니다.

1. 보조 함수 bin(n, x) 작성

• 빈 문자열 res를 생성합니다.
• n이 0보다 큰 동안 반복하며, n을 2로 나눈 나머지를 res에 추가하고 n을 2로 나눕니다.
• res를 뒤집어 올바른 이진수 순서로 만듭니다.
• res의 길이가 x보다 짧으면 앞쪽에 '0'을 채워 길이를 맞춥니다.
• res를 반환합니다.

2. 메인 함수 encode(n) 작성

• n이 0이면 빈 문자열을, 1이면 "0"을, 2이면 "1"을 반환합니다.
• x를 log₂(n)으로 설정합니다.
• 만약 2^(x+1) − 1이 n과 같다면, 이는 해당 자릿수의 마지막 숫자이므로 x를 1 증가시킨 후 그 길이만큼 '0'으로 채운 문자열을 반환합니다.
• 그 외의 경우에는 bin(n − 2^x + 1, x)의 결과를 반환합니다.

핵심 아이디어는 n이 속한 자릿수 구간(2^x ~ 2^(x+1)−1)을 찾은 뒤, 구간 시작점인 2^x를 빼고 1을 더함으로써 실제 이진수 표현과의 오프셋을 계산하는 것입니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string bin(int n, int x){
      string result = "";
      while(n>0){
         result += (n%2) + '0';
         n/=2;
      }
      reverse(result.begin(), result.end());
      while(x>result.size())result = '0' + result;
      return result;
   }
   string encode(int n) {
      if(n == 0)return "";
      if(n == 1)return "0";
      if(n==2) return "1";
      int x = log2(n);
      if(((1<<(x+1)) - 1) == n){
         string ans = "";
         x++;
         while(x--)ans+="0";
         return ans;
      }
      return bin(n - (1<<x) + 1, x);
   }
};
main(){
   Solution ob;
   cout << (ob.encode(23)) << endl;
   cout << (ob.encode(54)) << endl;
}

입력

23
54

출력

1000
10111

동작 원리 상세 분석

예제 1: n = 23
x = log₂(23) = 4입니다. 2⁵ − 1 = 31 ≠ 23이므로, bin(23 − 2⁴ + 1, 4) = bin(8, 4)를 호출합니다. 8의 이진수는 "1000"이고 길이가 이미 4이므로 최종 결과는 "1000"입니다.

예제 2: n = 54
x = log₂(54) = 5입니다. 2⁶ − 1 = 63 ≠ 54이므로, bin(54 − 2⁵ + 1, 5) = bin(23, 5)를 호출합니다. 23의 이진수는 "10111"이므로 최종 결과는 "10111"입니다.

이 알고리즘의 시간 복잡도는 O(log n)으로, 입력 크기에 비례해 로그 시간 안에 결과를 얻을 수 있어 매우 효율적입니다.