문제 소개
이번 글에서는 JavaScript로 해결할 수 있는 흥미로운 알고리즘 문제를 다뤄보겠습니다. 숫자 n을 입력받아, 해당 숫자의 2진수 표현 뒤에 가장 짧은 이진 문자열을 이어 붙여 만들 수 있는 5의 다음 배수를 반환하는 함수를 작성하는 것이 목표입니다.
예를 들어 숫자 8의 2진수는 '1000'입니다. 이 뒤에 이진 문자열을 하나씩 이어 붙여가며 그 결과값이 5로 나누어떨어지는지 확인하고, 조건을 만족하는 가장 짧은 문자열을 찾으면 됩니다.
해결 접근 방식
핵심 아이디어는 다음과 같습니다.
1. 입력받은 숫자를 2진수 문자열로 변환합니다.
2. 길이가 1인 이진 문자열부터 시작해, 가능한 모든 조합('0', '1', '00', '01', '10', '11' 등)을 생성합니다.
3. 각 조합을 원래 숫자의 2진수 뒤에 붙인 후, 그 값을 10진수로 변환하여 5로 나누어떨어지는지 검사합니다.
4. 조건을 만족하는 첫 번째(가장 짧은) 문자열을 찾으면, 최종 결과값을 반환합니다.
구현 코드
다음은 위 로직을 구현한 전체 코드입니다.
// 지정된 길이의 모든 이진 문자열 조합을 생성하는 함수
const generateAll = (num = 1) => {
const res = [];
let max = parseInt("1".repeat(num), 2);
for(let i = 0; i <= max; i++){
res.push(i.toString(2).padStart(num, '0'));
};
return res;
};
// 원본 숫자의 2진수 뒤에 이진 문자열을 붙여 5의 배수를 찾는 함수
const smallestMultiple = (num = 1) => {
const numBinary = num.toString(2);
let i = 1;
while(true){
const perm = generateAll(i);
const required = perm.find(binary => {
return parseInt(numBinary + binary, 2) % 5 === 0;
});
if(required){
return parseInt(numBinary + required, 2);
};
i++;
};
};
console.log(smallestMultiple(8));실행 결과
35
코드 설명
generateAll 함수는 주어진 길이만큼의 모든 이진 문자열 조합을 만들어 배열로 반환합니다. 예를 들어 num이 2라면 ['00', '01', '10', '11']을 생성합니다. padStart 메서드를 사용해 각 숫자를 고정된 자릿수의 이진 문자열로 맞춰주는 것이 포인트입니다.
smallestMultiple 함수는 while 반복문을 통해 이진 문자열의 길이를 1씩 늘려가며 조건을 만족하는 값을 탐색합니다. find 메서드 덕분에 조건을 처음 만족하는 문자열에서 바로 검색이 중단되므로 효율적입니다.
숫자 8의 경우, 8의 2진수 '1000' 뒤에 '11'을 붙인 '100011'은 10진수로 35이며, 35는 5의 배수입니다. 따라서 결과값으로 35가 출력됩니다.
마무리
이 문제는 문자열 조합 생성, 2진수와 10진수 간 변환, 나머지 연산 등 JavaScript의 기본기를 종합적으로 활용해야 하는 좋은 연습 문제입니다. 비슷한 방식으로 특정 숫자의 배수를 찾거나, 다른 진법 체계에 응용해볼 수도 있으니 여러분도 직접 변형해 보시길 추천합니다.