[BOJ 11005] 진법 변환 2 - 수학

[BOJ 11005] 진법 변환 2 - 수학

문제 링크

• https://www.acmicpc.net/problem/11005

문제 요약

• 10진법 수 N을 B진법(2~36진법)으로 변환하여 출력하는 문제
• 10 이상의 값은 A(10), B(11), ..., Z(35)로 표현

접근 방법

• 진법 변환 알고리즘: N을 B로 나눈 나머지를 구하고, N을 B로 나눈 몫으로 갱신하는 과정을 반복
• 나머지가 0~9이면 숫자로, 10~35이면 알파벳 A~Z로 변환
• 나머지를 구하는 순서가 역순이므로 마지막에 문자열을 뒤집어야 함

풀이 코드

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    int n(0);
    int b(0);
    std::cin >> n >> b;

    std::string result;

    // N을 B진법으로 변환
    while (n > 0) {
        int remainder(n % b);

        // 나머지가 10 미만이면 숫자, 10 이상이면 알파벳
        if (remainder < 10) {
            result += ('0' + remainder);
        } else {
            result += ('A' + remainder - 10);
        }

        n /= b;
    }

    // 결과를 뒤집어서 출력 (역순으로 계산되었으므로)
    std::reverse(result.begin(), result.end());
    std::cout << result << "\n";

    return 0;
}

시간/공간 복잡도

• 시간: O(log_B N) - N을 B로 나누는 횟수만큼 반복
• 공간: O(log_B N) - 결과 문자열 길이