정수형 숫자 하나가 주어졌다고 가정해 보겠습니다. 우리의 과제는 이 숫자의 자릿수를 재배열하여, 재배열 후 만들어진 새로운 수가 원래의 수, 즉 'number'로도 나누어 떨어지도록 만드는 것입니다.
다양한 입력·출력 시나리오 살펴보기
입력 − int number = 100035
출력 − 원래 수로 나누어 떨어지는 재배열 결과: 300105
설명 − 정수 100035가 'number'로 주어졌습니다. 이제 주어진 자릿수들을 재배열하여 만들어진 수가 100035로 나누어 떨어지도록 해야 합니다. 자릿수를 재배열한 결과 300105를 얻었으며, 이 수는 실제로 100035로 나누어 떨어집니다.
입력 − int number = 1000035
출력 − 원래 수로 나누어 떨어지는 재배열 결과: 3000105
설명 − 정수 1000035가 'number'로 주어졌습니다. 마찬가지로 자릿수를 재배열하여 만들어진 수가 1000035로 나누어 떨어져야 합니다. 자릿수를 재배열한 결과 3000105를 얻었으며, 이 수는 1000035로 나누어 떨어집니다.
입력 − int number = 28
출력 − 원래 수로 나누어 떨어지는 재배열 결과: -1
설명 − 정수 28이 'number'로 주어졌습니다. 자릿수를 재배열하면 82가 되는데, 이 수는 28로 나누어 떨어지지 않습니다. 따라서 출력은 -1입니다.
프로그램에서 사용된 접근 방식
이 문제의 핵심은 자릿수를 재배열한 수는 원래 수와 각 숫자(0~9)의 등장 횟수가 완전히 동일해야 한다는 점입니다. 따라서 원래 수의 2배부터 9배까지의 배수를 차례로 검사하면서, 자릿수 빈도가 원래 수와 일치하는 배수를 찾으면 그 값이 곧 답이 됩니다.
정수형 변수, 예를 들어 number를 입력받아 Rearrangement(number) 함수에 전달합니다.
Rearrangement(number) 함수 내부에서 다음을 수행합니다.
정수형 값을 저장하는 vector 타입 변수 vec(10, 0)을 생성합니다. 이 벡터는 0부터 9까지 각 숫자의 등장 횟수를 저장합니다.
total_count(number, vec) 함수를 호출하고 number와 vec을 매개변수로 전달하여 원래 수의 자릿수 빈도를 계산합니다.
i를 2부터 시작하여 i가 10보다 작을 때까지 FOR 반복문을 실행합니다. 반복문 안에서 temp를 number * i로 설정합니다.
정수형 값을 저장하는 또 다른 vector 타입 변수 vec_2(10, 0)을 생성합니다.
total_count(temp, vec_2) 함수를 호출하고 temp와 vec_2를 매개변수로 전달하여 해당 배수의 자릿수 빈도를 계산합니다.
equal(vec.begin(), vec.end(), vec_2.begin()) 조건이 참이면 두 수의 자릿수 구성이 동일하다는 의미이므로 temp를 반환하고, 모든 배수를 확인한 후에도 일치하는 경우가 없으면 -1을 반환합니다.
total_count(int number, vector<int> &vec_3) 함수 내부에서 다음을 수행합니다.
number가 0이 될 때까지 WHILE 반복문을 실행합니다. 반복문 안에서 vec_3[number % 10]++로 해당 자릿수의 개수를 1씩 증가시키고, number를 number / 10으로 갱신하여 다음 자릿수로 이동합니다.
예제
#include<bits/stdc++.h>
using namespace std;
void total_count(int number, vector<int> &vec_3){
while(number){
vec_3[number % 10]++;
number = number / 10;
}
}
int Rearrangement(int number){
vector<int> vec(10, 0);
total_count(number, vec);
for(int i = 2; i < 10; i++){
int temp = number * i;
vector<int> vec_2(10, 0);
total_count(temp, vec_2);
if(equal(vec.begin(), vec.end(), vec_2.begin())){
return temp;
}
}
return -1;
}
int main(){
int number = 100035;
cout<<"원래 수로도 나누어 떨어지는 재배열 결과: "<<Rearrangement(number);
return 0;
}
출력
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
원래 수로도 나누어 떨어지는 재배열 결과: 300105