[백준알고리즘] 10942번: 팰린드롬? -C++

[백준알고리즘] 10942번: 팰린드롬? -C++

10942번: 팰린드롬? (acmicpc.net)

10942번: 팰린드롬?

이전에 파이썬으로 풀다가 포기한 흔적이 있는 문제다.

 

문제를 보고 시간제한 있는 걸 보자마자 싸한 걸 느꼈다. 그래서 쉽게 구하는 것부터 생각하면서, 어떤 방법으로 문제를 풀어야 할지 고민했다.

 

그런데 생각보다 쉽게 풀렸다. 그래도 이전 파이썬 오답들이 정답 비율에 한몫했을 것 같다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

문제 풀이

먼저, 팰린드롬은 앞으로 읽나 뒤로 읽나 똑같은 말이다.

회문 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)

 

수열을 \(arr\)라 하자. (\(i\) 번째 값은 \(arr [i]\))

이때 기본적인 좌우대칭이 같은 값은 \(arr [i+t] == arr [j-t] (0 <= t <= (j - i) / 2 )\) 를 만족해야 한다.

 

그러고 나서 인덱스를 하나씩 증가하면서 확인해가면서 문제를 풀 방법을 찾았다.

1. 인덱스를 하나씩 증가시킨다.
2. 각 수의 인덱스를 리스트에 저장한다.
3. 같은 수의 인덱스가 각각 \(i\), \(j\)라고 할 때 \(i+1\)부터 \(j-1\) 까지가 팰린드롬이라면, \(i\) 부터 \(j\) 까지도 팰린드롬이다.
   
   • 사실 3가지 기준으로 팰린드롬이라 할 수 있다.
   • 자기 자신은 팰린드롬이다. (ex. 1)
   • 같은 두 수가 붙어있다면 팰린드롬이다. (ex. 1 1)
   • \(arr [i] == arr [j]\)이며 \(i+1\)부터 \(j-1\) 까지가 팰린드롬이라면, \(i\)부터 \(j\)까지도 팰린드롬이다. (ex. 1 2 1)

 

생각보다 간단히 풀려서 놀랐다. 아래가 성공한 코드다.

#include <cstdio>
#include <vector>
#include <list>

std::vector<std::list<int> > iEachIdx(100001, std::list<int>());
bool arrPalindrome[2001][2001] = { false, };

void findPalindrome(const int iIdx, const int iNum) {
	const std::list<int> &lstIdx = iEachIdx.at(iNum);
	for ( std::list<int>::const_iterator itIdx = lstIdx.begin(); itIdx != lstIdx.end(); ++itIdx ) {
		// 자기 자신은 팰린드롬
		if ( *itIdx == iIdx ) {
			arrPalindrome[iIdx][iIdx] = true;
		}
		// 두 수가 붙어있다면 팰린드롬
		else if ( iIdx - 1 < *itIdx + 1 ) {
			arrPalindrome[*itIdx][iIdx] = true;
		}
		// [i+1, j-1]가 팰린드롬이라면, [i, j]도 팰린드롬 (위치 i에서의 값과 위치 j에서의 값이 동일한 경우)
		else if ( true == arrPalindrome[*itIdx + 1][iIdx - 1] ) {
			arrPalindrome[*itIdx][iIdx] = true;
		}
	}
}

int main(void) {
	/* 입력 */
	int N;
	scanf("%d", &N);

	for ( int iIdx = 1; iIdx <= N; ++iIdx ) {
		int iNum;
		scanf("%d", &iNum);

		// 인덱스 입력
		iEachIdx.at(iNum).push_back(iIdx);
		
		/* 팰린드롬 구하기 */
		findPalindrome(iIdx, iNum);
	}

	/* 출력 (팰린드롬 유무) */
	int M;
	scanf("%d", &M);

	for ( int iCnt = 0; iCnt < M; ++iCnt ) {
		int S, E;

		// 문제(범위) 입력
		scanf("%d %d", &S, &E);

		printf("%d\n", (true == arrPalindrome[S][E]) ? 1 : 0);
	}

	return 0;
}

 

사실 시간 초과가 발생했었다. 위의 코드에서 배열(arrPalindrome)로 memoization 해서 팰린드롬을 만족 여부를 확인했는데, 이를 처음에는 set을 사용해서 시도했었다. set의 find를 사용하니 시간 초과가 발생했다. 이 정도는 아까운 것 같다.

 

아래는 시간 초과가 발생한 코드다. 사실상 거의 같다.

#include <cstdio>
#include <vector>
#include <list>
#include <set>

std::vector<std::list<int> > iEachIdx(100001, std::list<int>());
std::set<std::pair<int, int> > mapPalindrome;

void findPalindrome(const int iIdx, const int iNum) {
	const std::list<int> &lstIdx = iEachIdx.at(iNum);
	for ( std::list<int>::const_iterator itIdx = lstIdx.begin(); itIdx != lstIdx.end(); ++itIdx ) {
		// 자기 자신은 팰린드롬
		if ( *itIdx == iIdx ) {
			mapPalindrome.insert(std::make_pair(iIdx, iIdx));
		}
		// 두 수가 붙어있다면 팰린드롬
		else if ( iIdx - 1 < *itIdx + 1 ) {
			mapPalindrome.insert(std::make_pair(*itIdx, iIdx));
		}

		// [i+1, j-1]가 팰린드롬이라면, [i, j]도 팰린드롬 (위치 i에서의 값과 위치 j에서의 값이 동일한 경우)
		std::set<std::pair<int, int> >::iterator itPalindrome = mapPalindrome.find(std::make_pair(*itIdx + 1, iIdx - 1));
		if ( itPalindrome != mapPalindrome.end() ) {
			mapPalindrome.insert(std::make_pair(*itIdx, iIdx));
		}
	}
}

int main(void) {
	/* 입력 */
	int N;
	scanf("%d", &N);

	for ( int iIdx = 1; iIdx <= N; ++iIdx ) {
		int iNum;
		scanf("%d", &iNum);

		// 인덱스 입력
		iEachIdx.at(iNum).push_back(iIdx);
		
		/* 팰린드롬 구하기 */
		findPalindrome(iIdx, iNum);
	}

	/* 출력 (팰린드롬 유무) */
	int M;
	scanf("%d", &M);

	for ( int iCnt = 0; iCnt < M; ++iCnt ) {
		int S, E;

		// 문제(범위) 입력
		scanf("%d %d", &S, &E);

		std::set<std::pair<int, int> >::iterator itRet = mapPalindrome.find(std::make_pair(S, E));
		printf("%d\n", (mapPalindrome.end() != itRet) ? 1 : 0);
	}

	return 0;
}