BOJ1334 다음 팰린드롬 수

아이디어

---

주어진 수보다 큰 수 중에 팰린드롬 수를 찾아야하니 일단 입력받은 수에 1을 더하고 시작했다. 그렇게 하고는 문자열의 가운데 인덱스부터 시작해서 양쪽으로 넓어지며 숫자를 비교하는 방식. 넓어지며 비교할 때는 다음과 같은 조건분기를 거쳤다.

1. 왼쪽 수가 오른쪽 수보다 크면 오른쪽 수는 그냥 왼쪽 수로 바꾼다.
2. 왼쪽 수가 오른쪽 수보다 작으면 오른쪽 수부터 끝까지 전부 0으로 바꾸고 오른쪽 수 바로 왼쪽의 수에 1을 더하고 반복문을 다시 시작한다.
3. 2번에 걸리지 않았다면 팰린드롬 완성

이 방법은 잘 먹혔지만 1번 조건분기에서 문제가 있었다. 오른쪽 수를 왼쪽 수로 바꾼 후 그 오른쪽에 있는 수들도 모두 0으로 바꿔줘야 자릿수 올림이 됐던 것. 이 부분을 간과하고 테스트 케이스만 돌렸다가 몇번 실패했다.

#include <bits/stdc++.h>
using namespace std;

void NumStringAddition(string& numStr, int index) {
	for (int i = index; i >= 0; i--) {
		if (numStr[i] == '9')
			numStr[i] = '0';
		else {
			numStr[i] += 1;
			break;
		}
	}

	if (numStr[0] == '0')
		numStr = '1' + numStr;
}

int main() {
	string numStr;
	cin >> numStr;
	NumStringAddition(numStr, numStr.size() - 1);

	if (numStr.size() > 1) {
		while (true) {
			int left, right;

			if (numStr.size() % 2 == 0) {
				left = numStr.size() / 2 - 1;
				right = left + 1;
			}
			else {
				left = numStr.size() / 2 - 1;
				right = left + 2;
			}

			bool flag = false;
			while (true) {
				if (numStr[left] > numStr[right]) {
					numStr[right] = numStr[left];
					for (int i = right + 1; i < numStr.size(); i++)
						numStr[i] = '0';
				}
				if (numStr[left] < numStr[right]) {
					for (int i = right; i < numStr.size(); i++)
						numStr[i] = '0';
					NumStringAddition(numStr, right - 1);
					break;
				}
				if (left == 0) {
					flag = true;
					break;
				}
				left--;
				right++;
			}

			if (flag)
				break;
		}
	}

	cout << numStr;
	return 0;
}

하지만 포스팅을 작성하면서 발견한 사실인데, 이 문제는 그냥 문자열의 가운데부터 시작하지 않고 양 끝에서 가운데로 좁혀가며 비교한다면 전혀 괜찮았을 부분이라는 것. 오른쪽 오프셋이 낮은 자릿수부터 시작한다면 해당 숫자가 자릿수 올림이 된다고 해도 이전 숫자들을 고려할 필요가 없어지기 때문이다.

해답

---

한 번 문제를 해결하고 복기하며 생각난대로 다시 코드를 작성했다. 홀수 짝수를 구분하는 부분도 함께 사라지며 더 간결한 코드가 됐다.

#include <bits/stdc++.h>
using namespace std;

void NumStringAddition(string& numStr, int index) {
	for (int i = index; i >= 0; i--) {
		if (numStr[i] == '9')
			numStr[i] = '0';
		else {
			numStr[i] += 1;
			break;
		}
	}

	if (numStr[0] == '0')
		numStr = '1' + numStr;
}

int main() {
	string numStr;
	cin >> numStr;
	NumStringAddition(numStr, numStr.size() - 1);

	if (numStr.size() > 1) {
		while (true) {
			int left = 0, right = numStr.size() - 1;

			bool flag = false;
			while (true) {
				if (numStr[left] > numStr[right])
					numStr[right] = numStr[left];

				if (numStr[left] < numStr[right]) {
					for (int i = right; i < numStr.size(); i++)
						numStr[i] = '0';
					NumStringAddition(numStr, right - 1);
					break;
				}
				if (left == numStr.size() / 2 - 1) {
					flag = true;
					break;
				}
				left++;
				right--;
			}

			if (flag)
				break;
		}
	}

	cout << numStr;
	return 0;
}