프로그래머스_가장 긴 팰린드롬

2020-04-22 · 배운 것 · 5분 읽기

https://programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

팰린드롬이란?

앞뒤를 뒤집어도 똑같은 문자열

ex) abcdcba는 abc와 cba가 d를 사이에 두고 대칭이므로 길이가 7인 팰린드롬 문자열이다.

풀이방법

bool dp[i][j] -> i~ j까지가 팰린드롬 문자열이면 true, 아니면 false

기본적으로 초기화 해줄것
1) 자기자신은 팰린드롬 문자열이다. ex) a, b
2) 연속된 문자열은 팰린드롬 문자열이다. ex) aa, bb

//자기자신은 true
for (int i = 0; i < n; i++)
	dp[i][i] = true;

//이어져 있는 경우 ex) aa, bb
for (int i = 0; i < n - 1; i++)
{
	if (str[i] == str[i + 1])
	{
		dp[i][i + 1] = true;
		cnt = 2;
	}
}

이제 본격적인 dp 계산

for (int k = 2; k <= n - 1; k++)
	{
		for (int i = 0; i < n - k; i++)
		{
			int j = i + k;

			if (str[i] == str[j])
				if (dp[i + 1][j - 1] == true)
				{
					dp[i][j] = true;
					cnt = max(cnt, j - i + 1);
				}
		}
	}

k는 검사할 문자열의 길이, i는 검사할 문자열의 첫번째 글자, j는 검사할 문자열의 마지막 글자이다.

이렇게만 보면 사실 위의 부분이 이해가 안갈수있다. 그래서 한번 예를 하나가지고 시뮬레이션해보겠다.

ex) s = abcba

k =2 이고 str[i] == str[j] 가 성립할때

이때 dp[i + 1][j - 1]는 i+1 = j-1 이므로 당연히 성립할것이다. 그러므로 dp[i][j]는 true

k=4 일때 str[i] == str[j] 가 성립할때

이때 dp[i + 1][j - 1]는 아까 위에서의 dp[i][j] 이므로 성립할것이다. 그러므로 dp[i][j]는 true
그러므로 j - i + 1 = 5, 팰린드롬의 가장긴 문자열의 값은 5 이다.

이 풀이의 시간복잡도

이 문제가 시간이 얼마나 주어지는지 알수없지만 dp를 이용한 이 풀이방법은 시간복잡도가 O(n^2)이고 문자열의 길이는 2500이 최대이므로 (약 6,250,000개의 연산) 주어진시간이 0.0625‬초라도 풀수있다.

전체코드

#include <iostream>
#include <algorithm>

using namespace std;

bool dp[2501][2501];

int solution(string s)
{
	int answer = 0;
	string str = s;
	int n = str.size();
	int cnt = 1;

	//자기자신은 true
	for (int i = 0; i < n; i++)
		dp[i][i] = true;

	//이어져 있는 경우 ex) aa, bb
	for (int i = 0; i < n - 1; i++)
	{
		if (str[i] == str[i + 1])
		{
			dp[i][i + 1] = true;
			cnt = 2;
		}
	}

	for (int k = 2; k <= n - 1; k++)
	{
		for (int i = 0; i < n - k; i++)
		{
			int j = i + k;

			if (str[i] == str[j])
				if (dp[i + 1][j - 1] == true)
				{
					dp[i][j] = true;
					cnt = max(cnt, j - i + 1);
				}
		}
	}
	cout << cnt;

	answer = cnt;

	return answer;
}

후기

다시보니 명확하게 설명 못한거 같은데 코드를 천천히 보시면 이해가 가실겁니다. ㅠ