[6. 문자열] 6.2 밑수 바꾸기

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

// main에서 vector 형태로 출력하기위한 기본 셋팅 

---

Q 6.2 밑수 바꾸기

문자열 하나와 두 개의 정수 b1,b2가 주어졌을 때, 정수의 밑수를 바꾸는 프로그램을 작성하시오.
ex) 615, b1 =7, b2=13 ====> (6*7² + 1*7 + 5*1) 의 숫자를 (1*13² + 10*13 + 7*1) 의 형태로 바꾸어 1A7이 출력되도록 해야함

---

먼저 b1의 결과를 10진수로 바꾼뒤 해당숫자 mod b2 를 이용해서 만들면된다.
해당내용의 소스코드와 결과는 다음과 같다.

// 6.2 밑수 바꾸기#include<string>
#include<numeric>
#include<cctype>
 
std::string ConstructFromBase(int num_as_int, int base)
{
    return num_as_int == 0 ? "" : ConstructFromBase(num_as_int / base, base)+
        static_cast<char>(num_as_int % base >= 10 ? 'A' +
            num_as_int % base - 10 :'0' + num_as_int % base);
}
std::string ConvertBase(const std::string& num_as_string, int b1, int b2)
{
    bool is_negative = num_as_string.front() == '-';
    int num_as_int = std::accumulate(begin(num_as_string) +
        is_negative, end(num_as_string), 0, [](int x, char c)
        {return x * 7 + (isdigit(c) ? c - '0' : c - 'A' + 10); });
    return (is_negative ?"-":"")+(num_as_int==0 ?"0":ConstructFromBase(num_as_int,b2));
}

길이를 n 이라고 할때 시간복잡도는O(n(1+log_b2b1))이 된다.

 // main std::cout << "6-2 " << ConvertBase("615", 7, 13) << std::endl;