본문 바로가기

알고리즘

Palindrome Numbers

문제 요약 : 
좌우가 대칭이 palindrome 수가 있습니다. 1, 2, 3, 4, ... 9, 11, 22, 33, ... 으로 순서가 있으며, 각 palindrome 숫자마다 차례대로 인덱스가 부여됩니다. 이러한 상황에서 인덱스를 주면 해당 인덱스의 palindrome 숫자를 구하는 문제입니다.


해결 방법 : 
일단 palindrome은 좌우가 대칭이므로 숫자의 반만 생각하면 됩니다.
저는 자리수별로 생각을 했는데,
1자리 수 = 1, 2, ... , 9까지 모두 9개가 있습니다.
2자리 수 = 11, 22, .. , 99까지 모두 9개가 있습니다.
3자리 수 = 101, 111, 121, ..., 191, 202, 212, ...292, .... , 999 까지 9 * 10개(90)가 있습니다.
이런 식으로 하는데,

자세히 살펴 보면,
1자리 수와 2자리 수는 모두 1자리만 보고 해당 자리수에서 나올 수 있는 가지수를 생각할 수 있습니다.
마찬가지로 3자리 수는 앞의 두자리 수만 가지고 가지수를 결정할 수 있고, 4자리수는 3자리수와 동일한 가지수를 가집니다.
이런 식으로 각 자리수 마다 나올 수 있는 가지수를 구하고 이를 누적하면 n자리수에서의 마지막 인덱스 값을 알 수 있습니다.(이 값을 배열에 저장해둡니다..)
예를들어, 1자리수는 9, 2자리수는 18, 3자리수는 108, ...

그리고 각 자리수마다 시작수를 저장해 둡니다. 
예를들어, 1자리수는 1, 2자리수는 1, 3자리수는 10, 4자리수는 10, ...
왜냐하면 1자리수는 1로 시작하고, 2자리수는 11로 시작하는데 11중에 1만 보면 되기 때문입니다.

이런식으로 테이블을 구성하고, 최대로 들어오는 index값이 2 * 10^9이므로 이 값 이상의 값이 누적값으로 나올때까지 배열을 구성하면 됩니다.

 자리수 1 2
누적 인덱스  18  108 198
 시작수 10 10 

배열을 다 구성하면 인풋을 받고, 받은 수의 자리수를 판단할 수 있겠죠.
예를 들어, 입력 인덱스가 13이라면 누적 인덱스를 차례대로 돌면서 누적인덱스가 입력 인덱스보다 큰 부분을 찾습니다. 그러면 그 인덱스가 입력 인덱스의 자리수가 되는거죠.
위의 표를 보면 18이 13보다 크므로 현재 인덱스의 자리수는 2가 되는 겁니다. 

자리수를 구했으면 이제 palindrome값을 찾아야 합니다.
만약 입력 인덱스가 N이고, 현재 자리수가 i라하면, 

찾아야할 palindrome의 절반에 해당하는 수 = N - lastIndex[i - 1] - 1

이 됩니다.
여기서 lastIndex배열은 누적 인덱스 배열입니다.
이런 식으로 숫자의 반을 구했으면 index가 홀수이냐, 짝수이냐에 따라 출력만 약간 다르게 해주면 끝납니다.

그리고 만약 누적 인덱스와 입력 인덱스가 동일하다면 결과는 그 자리수만큼 9로 채운 숫자이죠.
예를 들어, 입력 인덱스가 18이 들어왔다면, 이는 누적인덱스 표에 있는 18과 같으므로 2자리 수이고, 이 2자리수가 9로 채워지므로 답은 99가 됩니다.

결과 : Accepted

소스 코드


#include<iostream>
#include<cmath>
#include<string>

using namespace std;

const long long MAX_NUMBER = 2000000000;

long long N;
long long lastIndex[100];
long long startNumber[100];
int lastDigit;
int digit;
bool isLast;
string result;



void makeLastIndex() {
	startNumber[0] = 0;
	lastIndex[0] = 0;
	for(int i = 1; i <= 99; i++) {
		startNumber[i] = (int)pow(10.0, ceil(i / 2.0) - 1);
		lastIndex[i] = lastIndex[i - 1] + 9 * startNumber[i];
		if(lastIndex[i] >= MAX_NUMBER) {
			lastDigit = i;
			break;
		}
	}
}



int main() {
	//freopen("input.txt", "r", stdin);
	makeLastIndex();
	

	while(true) {
		cin >> N;
		if(N == 0) break;
		//end of input
		
		isLast = false;
		digit = lastDigit;
		//end of init

		for(int i = 1; i <= lastDigit; i++) {
			if(N == lastIndex[i]) {
				isLast = true;
				digit = i;
				break;
			} else if(N < lastIndex[i]) {
				digit = i;
				break;
			}
		}	//end of deciding digit

		result = "";
		if(isLast) {	
			//해당 자리 수의 마지막 인덱스일 경우 9가 자릿수만큼 채워진다.
			for(int i = 0; i < digit; i++) {
				result += "9";
			}
		} else {	
			long addingNumber = N - lastIndex[digit - 1] - 1;
			//palindrome의 반만 구한다.
			long halfResult = startNumber[digit] + addingNumber;
			//구한 값을 출력하기 쉽게 하려고 char[]에 넣는다.
			char halfResultString[20];
			sprintf(halfResultString, "%d", halfResult);

			//출력한다.
			int halfDigit = (int)ceil(digit / 2.0) - 1;
			for(int i = 0; i <= halfDigit; i++) {
				result += halfResultString[i];
			}

			if(digit % 2 == 0) {
				result += halfResultString[halfDigit];
			}

			for(int i = halfDigit - 1; i >= 0; i--) {
				result += halfResultString[i];
			}
		}

		cout << result << endl;
	}
	return 0;
}

'알고리즘' 카테고리의 다른 글

Prime Gap  (0) 2010.08.28
The Tourist Guide  (0) 2010.08.03
Word Index  (0) 2010.07.31
Knights Move  (0) 2010.07.29