[BOJ 2745] 진법 변환 - [수학, 구현, 문자열]

[BOJ 2745] 진법 변환 - [수학, 구현, 문자열]

문제 링크

https://www.acmicpc.net/problem/2745

문제 요약

$B$진법 수 $N$을 입력받아 10진법으로 변환하여 출력한다. 알파벳 대문자는 10부터 35까지의 숫자를 나타낸다.

접근 방법

• 자료구조: std::string (입력받는 $N$의 각 자릿수를 확인하기 위함)
• 알고리즘: 다항식 계산 (Horner's Method 응용)
• 핵심 아이디어:
  • 문자열의 앞에서부터 읽으며 현재까지의 결과에 진법 $B$를 곱하고, 새로운 자릿수 값을 더해준다.
  • 문자가 '0'~'9'인 경우와 'A'~'Z'인 경우를 분기 처리하여 정수형 값으로 변환한다.

풀이 코드

#include <iostream>
#include <string>

using namespace std;

int main() {
    // 입출력 성능 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string n;
    int b;
    cin >> n >> b;

    long long result = 0;

    for (int i = 0; i < n.length(); i++) {
        int val;
        // 문자를 숫자로 변환
        if (n[i] >= '0' && n[i] <= '9') {
            val = n[i] - '0';
        } else {
            val = n[i] - 'A' + 10;
        }

        // 결과값 갱신: 이전 결과에 진법을 곱해 자릿수를 올리고 현재 값을 더함
        result = result * b + val;
    }

    cout << result << "\n";

    return 0;
}

시간/공간 복잡도

• 시간 복잡도: $O(L)$ ($L$은 문자열 $N$의 길이. 문자열을 한 번 순회함)
• 공간 복잡도: $O(L)$ (입력 문자열을 저장할 공간 필요)

실행 결과

• 메모리: 2024 KB
• 시간: 0 ms

핵심 포인트

1. 아스키 코드 활용: 'A' - 'A'는 0이 되므로, 여기에 10을 더해 'A'가 10임을 간단히 표현할 수 있다.
2. 오버플로우 방지: 결과값이 10억 이하라고 명시되어 있으나, 중간 계산 과정에서의 안전성을 위해 long long 타입을 사용하는 것이 권장된다.
3. 효율적 계산: pow 함수를 사용하지 않고 result = result * b + val 식을 사용하면 연산 횟수를 줄일 수 있다.

예제 확인

• 예제 1: ZZZZZ 36 입력 시
  • $Z = 35$
  • $35 \cdot 36^4 + 35 \cdot 36^3 + 35 \cdot 36^2 + 35 \cdot 36^1 + 35 \cdot 36^0 = 60466175$
  • 출력 결과: 60466175 (일치)