[알고리즘] 자릿수 분해하기

숫자 데이터를 처리하다 보면 각각의 자리를 직접 분해하여 가져와야 하는 경우가 생긴다. 자릿수를 구하는 알고리즘은 간단한데 자릿수를 분해하는 알고리즘은 조금 까다롭다.

1. 자릿수 분해란?

자연수의 자리를 하나씩 분해하는 것이다.

예를 들어 145를 자릿수 분해하면 일의 자리:1 십의자리: 4 백의 자리: 5 이렇게 분리할 수 있다.

 

자릿수를 분해하는 알고리즘은 크게 string을 이용하는 방법과 수학적인 방법을 떠올릴 수 있다.

 

2. 자릿수 분해 알고리즘

1) 반복문 이용하기

아이디어

중학교때 배운 자릿수의 개념을 이용하여 하나씩 가져오는 것이다.

구현

벡터를 이용하면 되는데 이 경우에 자릿수는 벡터의 크기이다.

#include <iostream>
#include<vector>

using namespace std;
int a, b;
vector<int> dig;

void digit(int n){
    while(n!= 0){
        dig.push_back(n%10);
        n /= 10;
    }
}
int main() {
    int num;
    cin >> num;
    digit(num);
    cout << "자릿수: " << dig.size() << "\n";
    int k = 1;
    for(int i=0; i<dig.size(); i++, k *= 10) cout << k << "의 자리: " << dig[i] << "\n";

    return 0;
}

다음은 위의 코드에 658463을 입력했을 때 출력값이다.

자릿수: 6
1의 자리: 3
10의 자리: 6
100의 자리: 4
1000의 자리: 8
10000의 자리: 5
100000의 자리: 6

 

2) string 이용하기

아이디어

int로 처리할 수 없는 매우 큰 자리를 처리해야 할 경우가 있다.

예를 들어 9,223,372,036,854,775,807이는 long long의 최대 범위인 19자리 자연수이다. 이 숫자를 넘어가면 overflow가 발생해서 string으로 숫자를 담아야 한다. string을사용하여 각각의 자릿수를 연산하는 경우에는 int로 형변환한 후에 연산해야 한다.

 

3. 예제

자릿수 분해 알고리즘을 활용한 문제들이다.

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

2231번: 분해합

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

4673번: 셀프 넘버

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

12348번: 분해합 2

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

1039번: 교환