#10942 팰린드롬? - 미완

팰린드롬(palindrome): 앞뒤를 뒤집어도 똑같은 문자열

 

# 문제

 

# 입력 및 출력

 

# 풀이

시간이 0.5초 인 것을 보아 적절한 알고리즘을 찾지 못하면 시간초과가 걸릴 것 같은데

일단 시간은 배제하고 단순한 코드로 작성해보았다

#include <iostream>
using namespace std;
int N, M, s, e, isPD;
int dp[2001];

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> dp[i];
	}
	cin >> M;
	for (int i = 0; i < M; i++) {
		isPD = 0;
		cin >> s >> e;
		for (int j = s; j <= e; j++) {
			if (dp[j] != dp[e - j + 1]) {
				isPD++;
			}
		}
		if (isPD != 0) cout << 0 << endl;
		else cout << 1 << endl;
	}
}

역시나 시간 초과가 걸린다

M의 범위가 1 ≤ M ≤ 1,000,000 인데다가 안에 for문이 하나 더 있어서 시간 복잡도가 늘어난 것 같다

일단 M만큼은 무조건 돌아야 하기 때문에 안에 있는 for문을 줄이는 방법을 찾아야 할 것 같다

 

https://4z7l.github.io/2021/04/07/algorithms-boj-10942.html

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

 

이사람처럼 나중에 시간복잡도 계산이랑 전부 예외 케이스 찾는 방식으로 블로그 안보고 다시 풀어봐야겠다