이 글에서는 십진수를 나타내는 문자열을 받아 특정 규칙에 따라 0과 1로만 이루어진 문자열로 변환(인코딩)하는 JavaScript 함수를 만드는 방법을 알아봅니다.
문제 정의
우리는 십진수를 표현하는 문자열을 입력받는 함수를 작성해야 합니다. 이 함수는 다음 규칙에 따라 각 숫자를 이진 형태로 인코딩해야 합니다.
n의 각 자릿수 d에 대해:
- d의 비트 수를 k라고 할 때, 0을 (k-1)번 반복해서 쓴 뒤 그 뒤에 1을 붙입니다.
- 이어서 숫자 d 자체를 이진수 문자열로 작성합니다. 이때 가장 오른쪽 비트가 최하위 비트(LSB)입니다.
- 마지막으로 위 두 부분을 연결(concatenate)하여 해당 자릿수 d의 인코딩을 완성합니다.
마지막으로 n의 모든 자릿수에 대해 얻은 결과들을 차례대로 이어 붙이면 전체 인코딩이 됩니다.
예를 들어, 숫자 2는 0110으로, 숫자 3은 0111로 인코딩됩니다. 숫자 2와 3은 한 자리(3비트)이므로 '01' 접두사가 붙고, 뒤에 각각 '10', '11'이라는 이진 표현이 붙습니다.
구현 코드
다음은 위 규칙을 구현한 코드입니다.
const str = '77338855';
const encodeNumString = (str = '') => {
// 0~9 각 숫자의 인코딩 값을 생성하는 내부 함수
const buildarray = (string = '') => {
let n = string.split(''), res = '';
n.forEach(x => {
let num = Number(x).toString(2);
num = '0'.repeat(num.length - 1) + '1' + num;
res += num;
});
return res;
}
// 0부터 9까지 각 숫자의 인코딩을 미리 계산
const arr = [];
let res = "";
for (let i = 0; i < 10; i++){
arr.push(buildarray(String(i)));
};
// 디코딩: 인코딩된 문자열을 원래 숫자 문자열로 복원
while (str.length){
for (let i = 0; i < 10; i++) {
if (str.startsWith(arr[i])) {
res += String(i);
str = str.slice(arr[i].length);
break;
}
}
}
return res;
};
console.log(encodeNumString(str));
출력 결과
콘솔 출력 결과는 다음과 같습니다.
001111001111011101110001100000011000001101001101
코드 동작 방식
이 코드의 흐름을 단계별로 살펴보겠습니다.
1. 각 숫자의 인코딩 미리 생성
buildarray 함수는 주어진 숫자를 이진수 문자열로 변환한 뒤, 그 길이보다 하나 적은 개수의 '0'과 '1'을 접두사로 붙여 고유한 코드를 만듭니다. 예를 들어 7은 이진수로 '111'(3비트)이므로 '001' + '111' = '001111'로 인코딩됩니다. 이런 방식은 각 코드가 서로 다른 길이를 가지면서도 접두사 충돌 없이 유일하게 구분되도록 보장합니다.
2. 디코딩 로직
흥미롭게도 위 예제 코드는 인코딩된 이진 문자열을 원래 숫자 문자열로 되돌리는 디코딩 과정을 보여줍니다. 미리 계산해 둔 0~9의 인코딩 배열(arr)과 startsWith() 메서드를 사용해 입력 문자열의 시작 부분이 어떤 숫자의 코드와 일치하는지 확인하고, 일치하면 해당 숫자를 결과에 추가한 후 처리된 만큼 문자열을 잘라냅니다. 이 과정을 문자열이 빌 때까지 반복합니다.
3. 시간 복잡도
각 단계에서 최대 10개의 코드와 비교하므로, 전체 시간 복잡도는 인코딩된 문자열 길이에 비례하여 O(n × 10), 즉 선형 시간에 가깝게 동작합니다. 덕분에 길이가 긴 문자열에서도 효율적으로 처리할 수 있습니다.