개요
매우 큰 수가 하나 주어졌을 때, 이 숫자를 회전(rotate)시켜 얻을 수 있는 모든 수 중에서 4로 나누어떨어지는 회전의 개수를 구하는 것이 목표입니다.
모든 회전을 실제로 수행하는 것은 비효율적이기 때문에, 4의 배수 판정 법칙을 활용합니다. 어떤 수의 마지막 두 자리가 4로 나누어떨어지면 그 수 전체도 4로 나누어떨어진다는 성질을 이용하는 것입니다.
예를 들어 숫자가 1234라면 회전 결과는 1234, 4123, 3412, 2341이 됩니다. 이 중 3412는 마지막 두 자리인 12가 4로 나누어떨어지므로 4의 배수입니다.
예제로 이해하기
입력 − num = 15324
출력 − 4로 나누어떨어지는 회전의 개수: 2
설명 − 가능한 회전은 다음과 같습니다.
15324, 41532, 24153, 32415, 53241
이 중 15324와 41532가 4로 나누어떨어집니다.
입력 − num = 848484
출력 − 4로 나누어떨어지는 회전의 개수: 6
설명 − 가능한 회전은 다음과 같습니다.
848484, 484848, 848484, 484848, 848484, 484848
모든 회전이 4로 나누어떨어집니다.
알고리즘 접근 방식
숫자를 문자열로 변환한 뒤 for 루프로 탐색하면서, 인접한 두 자리씩 짝을 지어 정수로 바꾸고 4로 나누어떨어지는지 검사합니다. 나누어떨어질 경우 카운트를 증가시킵니다.
숫자를 long long 타입의 num으로 받습니다.
Rotation_4(long long num) 함수는 num을 입력받아 4로 나누어떨어지는 회전의 개수를 반환합니다.
to_string(num)으로 num을 문자열 str로 변환합니다.
num의 자릿수는 length = str.length()로 구합니다.
두 자리 짝의 정수 값을 저장할 임시 변수 digit = 0을 선언합니다.
카운트 변수 count를 0으로 초기화합니다.
length가 1이라면 한 자리 숫자뿐이므로 digit = (str.at(0) - '0')으로 변환합니다.
digit을 4로 나누어 확인하고 결과를 1 또는 0으로 반환합니다.
i = 0부터 i < length - 1까지 for 루프로 str을 탐색합니다.
각 두 자리 짝은 회전 시 마지막 두 자리가 되므로, digit = (str.at(i) - '0') * 10 + (str.at(i+1) - '0')으로 두 자리 수를 만듭니다.
마지막 자리와 첫 번째 자리로 이루어진 짝도 digit = (str.at(length-1) - '0') * 10 + (str.at(0) - '0')으로 동일하게 처리하고, 4로 나누어떨어지면 count를 갱신합니다.
최종적으로 count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int Rotation_4(long long num){
string str = to_string(num);
int length = str.length();
int digit = 0, count = 0;
if (length == 1){
digit=(str.at(0)-'0');
if(digit%4 == 0){
return 1;
}
else{
return 0;
}
}
for (int i=0; i<(length-1); i++){
digit = (str.at(i)-'0')*10 + (str.at(i+1)-'0');
if(digit%4 == 0){
count++;
}
}
digit = (str.at(length-1)-'0')*10 + (str.at(0)-'0');
if(digit%4 == 0){
count++;
}
return count;
}
int main(){
long long num = 24040;
cout<<"Count of rotations divisible by 4 are: "<<Rotation_4(num);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of rotations divisible by 4 are: 4