[백준] 4096번: 팰린드로미터

 

 

#include <iostream>
#include <string>
using namespace std;

int numberArr[9];
int length;

bool isPalindrome()
{
	int half=length/2;
	
	for(int i=0; i<half; i++)
	{
		if(numberArr[i] != numberArr[length-1-i])
			return false;
	}
	return true;
}

void setArr()
{
	for(int i=length-1; i>0; i--)
	{
		if(numberArr[i] == 10)
		{
			numberArr[i-1]++;
			numberArr[i] = 0;
		}
	}
}

int main() {
	int count;
	string input;
	
	while(1)
	{
		count=0;
		cin >> input;
		length = input.length();
		
		if(input == "0")
			break;
		
		for(int i=0; i< length; i++)
		{
			numberArr[i] = input.at(i) -'0';
		}
	
		while(!isPalindrome())
		{
			count++;
			numberArr[length-1]++;
			setArr();
		}
		cout << count << endl;
	}
    
	return 0;
}

 

1. Palindrome이라는 것의 개념과 Palindrome 임을 확인하는 저성능의 알고리즘을 알아보는 시간이 되었다. Palindrome에 관해 알아보는중 O(N) 만에 확인하는 manacher 알고리즘이 있음을 알아냈고 추후에 알아볼 예정이다.

 

2. 문제를 해결하기 위해 필요한 배열을 매번 필요한 만큼 할당하는 것보다, 문제가 요하는 최대 크기의 배열을 일단 만들어 놓고 다른 변수를 통해 그 안에서 참조하는 범위를 제한하는 방식을 통하여 번거로움을 줄일 수 있었다.