C++로 길이 'k'의 모든 부분 문자열을 'b'진법에서 10진수로 변환하는 방법

이 튜토리얼에서는 주어진 문자열에서 길이가 'k'인 모든 부분 문자열을 추출하고, 이를 'b'진법의 수로 간주하여 10진수로 변환하는 프로그램을 C++로 구현하는 방법을 알아봅니다.

문제의 조건은 다음과 같습니다. 길이가 일정한 하나의 문자열이 주어지며, 우리는 이 문자열에서 크기가 'k'인 부분 문자열들을 순서대로 가져온 뒤, 각 부분 문자열이 'b'진법으로 표현된 수라고 가정하고 이에 대응하는 10진수 값을 계산해야 합니다.

동작 원리

변환 과정은 다음과 같이 진행됩니다.

1. 문자열의 시작 위치를 한 칸씩 이동하면서 길이 'k'의 부분 문자열을 추출합니다.
2. 추출한 부분 문자열의 각 자릿수에 대해, 해당 자릿값(숫자)에 진법의 거듭제곱(b^자릿수)을 곱합니다.
3. 오른쪽 자릿수부터 왼쪽으로 이동하며 계산한 값들을 모두 더하면 10진수 값이 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 부분 문자열을 10진수로 변환하는 함수
int convert_substrings(string str, int k, int b){
    for (int i = 0; i + k <= str.size(); i++){
        // 부분 문자열 추출
        string sub = str.substr(i, k);
        // 10진수 값 계산
        int sum = 0, counter = 0;
        for (int i = sub.size() - 1; i >= 0; i--){
            sum = sum + ((sub.at(i) - '0') * pow(b, counter));
            counter++;
        }
        cout << sum << " ";
    }
}
int main(){
    string str = "12212";
    int b = 3, k = 3;
    convert_substrings(str, b, k);
    return 0;
}

실행 결과

17 25 23

결과 해석

위 예제에서 입력 문자열은 "12212"이고, 진법 b는 3, 부분 문자열의 길이 k는 3입니다. 따라서 추출되는 부분 문자열은 "122", "221", "212" 세 개입니다.

각각을 3진법으로 해석하여 10진수로 변환하면 다음과 같습니다.

- "122" → 1×9 + 2×3 + 2×1 = 17
- "221" → 2×9 + 2×3 + 1×1 = 25
- "212" → 2×9 + 1×3 + 2×1 = 23

이처럼 슬라이딩 윈도우 방식으로 부분 문자열을 하나씩 이동시키며 자릿값 계산만 수행하면, 별도의 복잡한 라이브러리 없이도 간단하게 진법 변환 문제를 해결할 수 있습니다.