백준(BOJ) 13235번 팰린드롬 (Palindromes)

안녕하세요? 오늘은 백준 알고리즘 사이트에 있는 문제 중 하나인 13235번 팰린드롬을 풀어보겠습니다. 문제 번호가 13231 이었으면 더 의미가 있었을 텐데 아쉽습니다... 하하... 농담은 이정도로 하고 본격적으로 문제를 풀어보겠습니다.

팰린드롬이란 문제에서 설명하듯이 뒤로 읽으나 앞으로 읽으나 똑같은 단어를 말하는데요, 이는 Mirror alphabet과 혼동할 수 있지만 정확히는 다른 용어입니다. 위키백과에서는 이렇게 설명하고 있네요

"회문(回文) 또는 팰린드롬(palindrome)은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말이다. 보통 낱말 사이에 있는 띄어쓰기나 문장 부호는 무시한다."

따라서 주어진 문장이 팰린드롬이면 true를 아니면 false를 출력하는 문제입니다. 

제가 이 문제를 풀기 위해 접근한 방식은 문장을 분할 하는 겁니다. 문장을 둘로 나눠 앞 쪽을 pre, 뒤 쪽을 post로 정의해서 이 둘의 순서가 팰린드롬이 성립되기에 적합한지 판단해서 해결하는 방식을 생각했습니다.

제가 생각해낸 방법을 사용하기 위해서는 다음과 같은 두 가지를 주의깊게 고려해야 합니다. 

1. 문장이 length가 홀수인지, 짝수인지

2. pre와 post를 어떤 방식으로 비교할 것인지

만약 문장의 길이가 짝수면 그냥 반으로 나누면 되지만, 홀수라면 정확히 반으로 나눠지지 않죠, 그래서 홀수라면 가운데에 위치한 수를 제외한 나머지를 post로 분류하여야 합니다. 다음과 같이 말이죠.

먼저 짝수 길이의 문장입니다.

이런식 자르고 앞 쪽을 pre, 뒤 쪽을 post로 잡았습니다.

다음은 홀수 길이의 문장입니다.

이렇게 가운데에 위치한 1개의 알파벳을 기준으로 앞을 pre, 뒤를 post로 잡았습니다.

이제 2번에 대한 얘기로 넘어가도록 하겠습니다.

저는 pre와 post를 비교하기 위해 stack 자료구조를 사용했습니다.

stack은 LIFO(Last In, First Out)구조이기 때문에 주어진 문제를 해결하기에 적합하다 판단했습니다.

주어진 문제에서 I, a, o가 차례대로 pre에 위치하면 이 pre를 스택에서 꺼냈을 땐, o, a, I의 순서로 꺼내어집니다. 그리고 이 순서가 post와 일치하면 이 문장은 팰린드롬의 조건을 만족한다고 판단할 수 있습니다.

다음은 소스코드입니다.

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

bool compPreAndPost (int start_idx, stack<char> pre, string input) {
	while (pre.size() != 0) {
		if (pre.top() != input[start_idx++])
			return false;
		else {
			if(!pre.empty())
				pre.pop();
		}
	}
	return true;
}

bool isPalindrome(string input) {
	int inputLength = input.size();
	int start_idx;
	// input pre alphabet
	stack<char> pre;
	for (int i = 0; i < inputLength / 2; i++) {
		pre.push(input[i]);
	}

	// if input length is even, then set starting index to input length
	if (inputLength % 2 == 0) {
		start_idx = inputLength/2;
		if (compPreAndPost(start_idx, pre, input))
			return true;
		else
			return false;
	}
	// if input lengh is odd, then set starting index to input length + 1
	else {
		start_idx = inputLength/2 + 1;
		if (compPreAndPost(start_idx, pre, input))
			return true;
		else
			return false;
	}
}

int main() {
	string input;
	cin >> input;
	
	if (isPalindrome(input))
		cout << "true" << endl;
	else
		cout << "false" << endl;
	return 0;
}

구현 설명입니다.

먼저 main()함수에서 문장을 입력받습니다. 그리고 이를 isPalindrome()함수에 넘겨주어 해당 문장이 Palindrome인지 확인 합니다. 그리고 만약 맞으면 true를 출력하고 아니면 false를 출력하도록 했습니다.

isPlaindrome()함수는 string타입의 input을 받고 bool타입을 output으로 하는 함수입니다. 이 함수에서는 넘겨받은 input이 Palindrome인지 확인합니다. 그리고 이 함수에서 위에서 언급되었던 1번 과정, pre, post를 나누는 과정을 진행합니다. post는 시작 인덱스만 찾아내면 위치가 자명해지므로 별도로 저장하여 관리하진 않았습니다.

그리고 이를 cmpPreAndPost()로 넘겨주어 이 둘을 비교하고 이 둘이 서로 역순 관계계라면 true, 그렇지 않으면 false를 리턴하도록 하였습니다.

cmpPreAndPost()함수는 int타입, stack 타입, string 타입을 input으로 하며, bool 타입을 output으로 하는 함수입니다. start_idx는 string타입의 input에서 post에 해당하는 알파벳의 시작 위치를 가리킵니다. 그리고 stack타입의 pre는 앞에서 정의했던 pre입니다. 스택에 있는 pre와 input에 있는 post가 서로 역순이면 true, 그렇지 않으면 false를 리턴합니다. 여기서 좀 더 연산 시간을 단축시키기 위하여 비교과정에서 하나라도 어긋나면 더이상의 비교는 무의미함으로 바로 false를 리턴하도록 구현하였습니다. 그리고 stack을 pop할 때, memory access violation을 방지하기 위해 현재 스택이 비어있는지를 확인하는데 사실, 로직상 이 부분은 생략하여도 됩니다. 그러나 안전장치로 마련해두었습니다.

이상으로 포스팅을 마치겠습니다.

감사합니다.