넥슨 코딩테스트 기출 - ANUMBER
이번 포스팅에서는 넥슨 게임프로그래밍직군 테스트에 나왔던 문제인 A-NUMBER라는 문제의 풀이에 대해 포스팅 하고자 한다.
문제가 제법 어렵지만 차근차근 풀다보면 또할만하다.
제곱한 수의 끝에 자기 자신이 나오려면?
우선 가장먼저 해결해야될 문제는1~21억사이의 숫자 x에 대해 F(x)가 참인지 판별하는 방법이다.
정수를 문자열로 바꾼뒤 비교를 해도 되겠지만 얼핏봐도 꽤나 시간이 많이 소요될법한 전략이다. PASS
그렇다면 어떤식으로 접근을 해야 할까?
곱셈이 덧셈을 반복한것이라는 것에 한번 주목하여 F(x)가 참인 수들을 한번 살펴보자
5 -> 10 -> 15 -> 20 -> 25
625 -> 1250 -> 1875 -> ............... -> 390000 -> 390625
뭔가 눈에 보이는게 있는가?
그렇다 마지막으로 더하기 직전에 뒷자리가 0으로 채워져야 함을 볼수 있다.
다시말해 (x)*(x-1)은 10^xLength의 배수여야 x^2에서 뒷자리에 x가 나타날수 있다.
- xLength는 x라는 숫자의 길이를 의미 x가 1이면 xLength는 1, x가 123이면 xLength는 3, x가 111이면 Length 는 3
이런 판별법을 코드로 옮기면 다음과 같다.
int GetLength(long long num); // 숫자의 길이를 구하는 함수
long long tenPowers[MAX_POWER]; // 10의 제곱수들을 저장할 배열
// F(num)
bool FJudge(long long num)
{
long long mul = (num) * (num - 1);
int numLength = GetLength(num);
if (mul % tenPowers[numLength] == 0)
{
return true;
}
return false;
}
판별은 빨라졌지만 판별해야할 수가 너무 많다!
이제 판별자체는 굉장히 쉬워졌다. 그럼에도 아직 이 문제를 풀기에는 역부족이다.
아무리 판별이 빨라졌다 한들 판별해야할 수가 21억개고 이는 너무 큰 숫자이고 이렇게 많은 숫자를 판별하는데는 너무나도 많은 시간이 소요된다.
따라서 판별해야될 수 자체를 줄여주는 작업이 필요하다. 어떻게 하면 줄일수 있을까?
10^xLength의 배수는 바꿔말해 해당 숫자를 소인수 분해했을때 2와 5가 최소 xLength개씩 있어야 한다는 것을 의미한다. 즉 (x)*(x-1)을 소인수 분해 했을때 2와 5가 최소 xLength개씩 있어야 된다는 말이다.
그런데 잘 살펴보면 x와 x-1둘중 한쪽에 (2*5*5) 이렇게 2와 5가 중복으로 들어간 수는 절대 있을수 없음을 알수 있다.
n의 배수에다가는 1을 n번 더해야만 다시 n의 배수가 될수 있기 때문에 x와 x-1이 둘다 같은수의 배수일수는 없다.
결국 x와 x-1이 각각 2^xLength혹은 5^xLength의 배수여야 함을 알수 있다.
*한쪽이 10^xLength인 경우도 되지 않을까 생각할수 있는데 10^n은 길이가 n+1이다. 그래서 한자리가 부족하기 때문에 될수가 없다.
결국 ((a*2^xLength) * (b*5^xLength)) % 10^xLength = 0인 값을 찾고자 하는것이고 어차피 한쪽이 정해지면 남은 한쪽 역시 정해지는 것이니(x*(x-1)의 관계기때문) 개수가 더 적을것 같은 (b*5^xLength)들을 후보로 설정해 보자.
5^xLength의 배수중 10^xLength보다 작은수들을 찾아내 후보로 등록하면된다.
이를 코드로 옮기면 아래와 같다.
const int MAX_POWER = 10; // 지수의 최대 크기
long long fivePowers[MAX_POWER]; // 5의 제곱수들을 저장할 배열
long long tenPowers[MAX_POWER]; // 10의 제곱수들을 저장할 배열
set<long long > candidateNum; // 후보들
// 후보들을 구함 (5^xLength의 배수중 10^xLength보다 작은 값들)
for (int i = 0; i < MAX_POWER; i++)
{
candidateNum.insert(fivePowers[i]);
long long scale = 2;
while (scale * fivePowers[i] < tenPowers[i])
{
candidateNum.insert(scale * fivePowers[i]);
scale++;
}
}
이제 구해진 후보들을 판별하기만 하면 끝!
이제는 이 set에 들어간 수를 x혹은 x-1이라고 가정하고 판별을 해보면된다
num이 x라고 가정하면 F(num)이 참인지를 검사해서 참이면 num을 set에 넣어주고 num이 x-1이라고 가정할경우는 F(num+1)이 참인지를 검사해서 참이면 (num+1)을 set에 넣어주면된다.
bool FJudge(long long num); // F(num)
set<long long > candidateNum; // 후보들
set<long long > ans; // F(x)가 참인 수들
// 이제 각 후보들에 대한 검사를 실시
for (auto num : candidateNum)
{
// num이 x라고 가정할때
if (FJudge(num))
{
ans.insert(num);
}
// num이 x-1이라고 가정할때
if (FJudge(num + 1))
{
ans.insert(num + 1);
}
}
전처리된 데이터를 이용하여 쿼리에 대한 답 출력
이제는 전처리를 쭉하고 들어오는값 받아서 뭐 이분탐색을 하던 선형탐색을 하던 하면된다.
set<long long > ans; // F(x)가 참인 수들
int ansNum = -1;
// 돌면서 크거나 같은 수를 발견하면 브레이크
for (auto num : ans)
{
if (num >= n)
break;
ansNum = num;
}
// 출력
cout << ansNum << endl;
전체 코드
#include <iostream>
#include <set>
using namespace std;
int GetLength(long long num); // 숫자의 길이를 구하는 함수
bool FJudge(long long num); // F(num)
const int MAX_POWER = 10; // 지수의 최대 크기
long long fivePowers[MAX_POWER]; // 5의 제곱수들을 저장할 배열
long long tenPowers[MAX_POWER]; // 10의 제곱수들을 저장할 배열
set<long long > candidateNum; // 후보들
set<long long > ans; // F(x)가 참인 수들
int main()
{
long long five = 1;
long long ten = 1;
// 제곱수들을 미리 구함
for (int i = 0; i < MAX_POWER; i++)
{
fivePowers[i] = five;
five *= 5;
tenPowers[i] = ten;
ten *= 10;
}
// 후보들을 구함 (5^xLength의 배수중 10^xLength보다 작은 값들)
for (int i = 0; i < MAX_POWER; i++)
{
candidateNum.insert(fivePowers[i]);
long long scale = 2;
while (scale * fivePowers[i] < tenPowers[i])
{
candidateNum.insert(scale * fivePowers[i]);
scale++;
}
}
// 이제 각 후보들에 대한 검사를 실시
for (auto num : candidateNum)
{
// num이 x라고 가정할때
if (FJudge(num))
{
ans.insert(num);
}
// num이 x-1이라고 가정할때
if (FJudge(num + 1))
{
ans.insert(num + 1);
}
}
// 이제 수를 입력 받아서
int n;
cin >> n;
int ansNum = -1;
// 돌면서 크거나 같은 수를 발견하면 브레이크
for (auto num : ans)
{
if (num >= n)
break;
ansNum = num;
}
// 출력
cout << ansNum << endl;
return 0;
}
// 숫자의 길이를 구하는 함수
int GetLength(long long num)
{
int numLength = 0;
while (num > 0)
{
numLength++;
num /= 10;
}
return numLength;
}
// F(num)
bool FJudge(long long num)
{
long long mul = (num) * (num - 1);
int numLength = GetLength(num);
if (mul % tenPowers[numLength] == 0)
{
return true;
}
return false;
}
문제 출처
