[알고리즘] 각 자릿수 구하기

안녕하세요.

여행벌입니다.

오늘은 알고리즘 문제를 풀 때 자주 쓰이는

각 자릿수 구하기 알고리즘에 대해서 포스팅해보도록 하겠습니다.

---

알고리즘 문제를 풀다 보면, 어떤 정수의 각 자릿수를 구해야 하는 경우가 자주 생깁니다.

 

예를 들어, 5자리 정수 54321이 Input으로 들어온다고 가정해봅시다.

54321이라는 값이 들어오면 우리는 5, 4, 3, 2, 1 이라는 값을 구해야 되는데요.

다음과 같이 구할 수 있습니다.

5 = 54321 / 10000

4 = ( 54321 % 10000 ) / 1000

3 = ( 54321 % 1000 ) / 100

2 = ( 54321 % 100 ) / 10

1 = ( 54321 % 10 )

간단한 규칙이 보이시나요? %와 / 을 이용해 자릿수를 간단하게 다룰 수 있습니다.

 

다른 예시를 하나 더 다뤄볼까요?

9236715 라는 값이 들어오면 위의 알고리즘을 어떻게 변형하면 될까요?

9 = 9236715 / 1000000

2 = ( 9236715 % 1000000 ) / 100000

3 = ( 9236715 % 100000 ) / 10000

6 = ( 9236715 % 10000 ) / 1000

7 = ( 9236715 % 1000 ) / 100

1 = ( 9236715 % 100 ) / 10

5 = ( 9236715 % 10 )

다음과 같이 구할 수 있습니다.

 

지금 예시들은 다 몇 자리 숫자인지 미리 알고 있는 경우인데요.

보통 알고리즘 문제는 Input의 범위가 다음과 같이 정해져 있습니다.

Input : N , 1 ≤ N ≤ 100,000

그렇다면 이런 상황에서는 어떻게 알고리즘을 구현할 수 있을까요?

다음과 같이 코드를 구현할 수 있습니다.

#include<iostream>

using namespace std;

int list[6];

int main(void) {
	// 1 ~ 100,000 사이의 숫자가 Input으로 들어온다.
	int ninput;
	cin >> ninput;
	// 2자리 ~ 6자리 숫자는 각 자릿수를 구해서 출력해준다.
	list[0] = ninput / 100000; // 십만의자릿수
	list[1] = (ninput % 100000) / 10000; //만의자릿수
	list[2] = (ninput % 10000) / 1000; //천의자릿수
	list[3] = (ninput % 1000) / 100; //백의자릿수
	list[4] = (ninput % 100) / 10; //십의자릿수
	list[5] = (ninput % 10); //일의자릿수

	for (int i = 0; i < 6; i++) {
		cout << list[i] << ' ';
	}
}

최대 자릿수를 안다면 항상 다음과 같이 코드를 구현해 배열에 각 자릿수를 저장할 수 있습니다.

하지만 언뜻 보기에는 6자리 숫자가 들어오면 문제가 없지만, 1~5자리 숫자가 들어오면 문제가 있어 보입니다.

다음 예시를 통해서 1 ~ 5 자리 숫자가 들어오면 알고리즘이 어떻게 작동하는지 알아보겠습니다.

4321 이라는 4자리 숫자가 들어왔다고 가정해봅시다.

list[0] = 4321 / 100000 = 0

list[1] = (4321 % 100000) / 10000 = 0

list[2] = (4321 % 10000) / 1000 = 4

list[3] = (4321 % 1000) / 100 = 3

list[4] = (4321 % 100) / 10 = 2

list[5] = (4321 % 10)  = 1

다음과 같이 배열에 저장이 됩니다.

즉 Ninput보다 큰 자릿수에는 0이 저장되는 것을 확인할 수 있습니다.

이 알고리즘을 잘 활용하면 다음과 같은 문제들을 쉽게 해결할 수 있습니다.

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

14954번: Happy Number

---

오늘 포스팅은 여기서 마치겠습니다.