[백준/C++] 다음 팰린드롬 수 (No. 1334)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 구현을 잘하면 쉽게 풀 수 있는 문제다.

 

잘 생각해보면 앞에서 i번째 수와 뒤에서 i번째 수를 서로 비교하고 그 후 두 수가 다르면 앞에서 뒤에서 i번째 수가 앞에서 i번째 수와 같도록 더해주면 된다.

 

뒤에 있는 수에 더해주는 이유는 당연히 뒤에 있는 수가 커지는게 앞에 있는 수가 커지는 것 보다 작은 수가 만들어지기 때문이다.

 

ex) 102 인 경우 앞에 1을 더한 202와 뒤에 9를 더한 111을 비교해 생각하면 이해가 쉽다.

 

만약 앞에서 i번째 수가 2고 뒤에서 i번째 수가 1이라면 뒤에서 i번째 수를 1 더해 2로 만들어 주면 된다.

반대로 앞에서 i번째 수가 1이고 뒤에서 i번째 수가 2라면 뒤에서 i번째 수를 9 더해 1로 만들어 주고 앞자리에 1을 더해주면 된다.

 

실제로 이러한 연산은 구현하면 문제를 쉽게 해결할 수 있다.

 

여기서 고려해야 할 점은 뒤에서 i번째 수를 더했을 경우 자릿수가 추가 돼 바뀔 수 있다.

그러므로 이로 인해 자릿수가 변경 되는지 체크해 반영해주면 문제를 쉽게 풀 수 있다.

 

 

[아이디어 정리]

1. 앞에서 i번째 수와 뒤에서 i번째 수를 비교한다.
2. 당연히 앞쪽에 있는 수가 커지는 것보다 뒤에 있는 수가 커지는 게 더 작은 수이므로 뒤에 있는 수를 앞에 있는 수와 같도록 만든다.
3. i번째 수에 N이라는 수를 더해서 총 숫자의 자릿수가 변경되는 경우가 생길 수 있으므로 자릿수 변경이 일어났는지 체크해 반영해준다.

 

 

Code

 

 

#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <cmath>
using namespace std;


bool plusC(vector<int> &v, int idx, int Num)
{	//idx에 Num을 더하는 것
	int nowN = Num;
	for (int i = idx; i >= 0; i--)
	{
		int tmpN = v[i]+Num;
		if (tmpN>=10)
		{
			
			Num = 1;
			v[i] = tmpN - 10;
			if (i == 0)
			{
				v.insert(v.begin(), 1);
				return true;
			}
		}
		else {
			v[i] = tmpN;
			return false;
		}
	}
	return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	string str;
	cin >> str;
	bool flag = true;
	int n = str.size();
	vector<int> v(n, 0);
	for (int i=0; i<str.size(); i++)
	{
		v[i] = str[i]-'0';
		if (str[i]!=str[n-1-i])
		{
			flag = false;
		}
	}
	if (flag)
	{
		plusC(v, n - 1, 1);
		n = v.size();
	}
	for (int i=n-1; i>=0; i--)
	{
		n = v.size();
		if (v[i]!=v[n-1-i])
		{
			if (v[i]<v[n-1-i])
			{
				v[i] = v[n-i-1];
			}
			else
			{
				if (plusC(v, i, 10 + v[n - 1 - i] - v[i])) {
					i++;
				};
				i++;
			}
		}
	}
	for (int i=0; i<v.size(); i++)
	{
		cout << v[i];
	}

	return 0;
}

---

 

아이디어는 쉽지만 생각보다 구현에 시간이 걸렸던 문제다.

실수로 뒷자리 수에 더해줘야 하는데 i를 뒷자리 index로 초기화 한 줄 알고 앞자리에 수를 더해주는 바람에 생긴 오류였다...

 

https://www.acmicpc.net/problem/1334