이진 형태의 숫자 s가 주어졌을 때, 아래 규칙에 따라 이 숫자를 1로 줄이는 데 필요한 총 단계 수를 구하는 것이 목표입니다.
현재 숫자가 짝수라면 2로 나눕니다.
현재 숫자가 홀수라면 1을 더합니다.
문제 이해하기
예를 들어 입력이 "1101"이라면 출력은 6이 됩니다. "1101"은 십진수로 13에 해당합니다. 과정을 하나씩 살펴보면 다음과 같습니다.
13은 홀수 → 1을 더해 14를 얻습니다.
14는 짝수 → 2로 나누어 7을 얻습니다.
7은 홀수 → 1을 더해 8을 얻습니다.
8은 짝수 → 2로 나누어 4를 얻습니다.
4는 짝수 → 2로 나누어 2를 얻습니다.
2는 짝수 → 2로 나누어 1을 얻습니다.
총 6번의 연산으로 1에 도달했으므로 정답은 6입니다.
해결 접근 방법
이 문제는 문자열 형태의 이진수를 직접 조작하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
이진수의 마지막 비트가 0이면 짝수이므로, 마지막 비트를 제거하면 곧 2로 나눈 것과 같습니다.
마지막 비트가 1이면 홀수이므로, 이진수 덧셈으로 1을 더해야 합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
addStrings()함수를 정의합니다. 이 함수는 두 개의 정수 배열 num1, num2를 받아 이진 덧셈을 수행합니다.결과를 저장할 배열 ret을 정의하고, carry := 0, sum := 0으로 초기화합니다.
num1과 num2를 뒤집어 낮은 자릿수부터 계산합니다.
i := 0, j := 0으로 설정한 뒤, i가 num1의 크기보다 작거나 j가 num2의 크기보다 작은 동안 반복합니다.
두 인덱스가 모두 유효하면 sum := carry + num1[i] + num2[j]를 계산하고, ret 끝에 sum mod 2를 추가한 후 carry := sum / 2로 갱신하며 i와 j를 각각 1 증가시킵니다.
i만 유효하면 sum := carry + num1[i]를 계산하고 같은 방식으로 처리한 뒤 i를 1 증가시킵니다.
그 외의 경우에는 sum := carry + num2[j]를 계산하고 같은 방식으로 처리한 뒤 j를 1 증가시킵니다.
반복이 끝난 후 carry가 남아 있으면 ret 끝에 carry를 추가합니다.
ret을 역순으로 순회하며 각 값을 문자에 더해 ans 문자열을 만들고, ans가 비어 있으면 "0"을 반환합니다.
addBinary()함수는 배열 a, b를 받아 addStrings(a, b)의 결과를 반환합니다.makeVector()함수는 문자열 v의 각 문자에서 '0'의 ASCII 값을 빼서 정수 벡터로 변환해 반환합니다.메인 로직에서는 ret := 0으로 초기화하고, x = makeVector(s)로 변환한 뒤 다음을 반복합니다.
x의 크기가 1보다 큰 동안 ret을 1 증가시킵니다.
x의 마지막 원소가 0이면 해당 원소를 삭제합니다(2로 나누기).
그렇지 않으면 크기 1짜리 temp 배열을 만들어 temp[0] = 1로 설정한 후, x := makeVector(addBinary(x, temp))로 갱신합니다(1 더하기).
최종적으로 ret을 반환합니다.
구현 예제
더 나은 이해를 위해 다음 C++ 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string addStrings(vector<int> num1, vector<int> num2){
vector<int> ret;
int carry = 0;
int sum = 0;
reverse(num1.begin(), num1.end());
reverse(num2.begin(), num2.end());
int i = 0;
int j = 0;
while (i < num1.size() || j < num2.size()) {
if (i < num1.size() && j < num2.size()) {
sum = carry + (num1[i]) + (num2[j]);
ret.push_back(sum % 2);
carry = sum / 2;
i++;
j++;
}
else if (i < num1.size()) {
sum = carry + (num1[i]);
ret.push_back(sum % 2);
carry = sum / 2;
i++;
}
else {
sum = carry + (num2[j]);
ret.push_back(sum % 2);
carry = sum / 2;
j++;
}
}
if (carry)
ret.push_back(carry);
i = ret.size() - 1;
string ans = "";
for (; i >= 0; i--)
ans += (ret[i] + '0');
return ans.size() == 0 ? "0" : ans;
}
string addBinary(vector<int>& a, vector<int>& b){
return addStrings(a, b);
}
vector<int> makeVector(string v){
vector<int> ret;
for (int i = 0; i < v.size(); i++)
ret.push_back(v[i] - '0');
return ret;
}
int numSteps(string s){
int ret = 0;
vector<int> x = makeVector(s);
while (x.size() > 1) {
ret++;
if (x.back() == 0) {
x.pop_back();
}
else {
vector<int> temp(1);
temp[0] = 1;
x = makeVector(addBinary(x, temp));
}
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.numSteps("1101"));
}입력
"1101"
출력
6
복잡도 분석
이진수 길이를 n이라 할 때, 홀수일 때마다 1을 더하는 연산은 최악의 경우 자릿수 전체를 확인해야 하므로 시간 복잡도는 O(n²), 공간 복잡도는 결과를 저장하는 벡터 때문에 O(n)입니다. 참고로, 연속된 1의 개수를 세며 한 번의 순회로 답을 구하는 O(n) 최적화 풀이도 존재합니다.