[Programmers] 가장 긴 팰린드롬

너무 어렵다.

그래서 다른 사람 블로그에서 2차원 배열을 이용한 방법을 참고하였다.

그런데 어찌 요런 생각을 해냈는지 정말 모를 일이다... ㅠ_ㅠ! 

 

// 참고사이트 : https://www.mstst33.com/programmers-the_longest_palindrome/201/

 

이차원 boolean 배열을 이용하여 팰린드롬인지 아닌지 체크를 해준다. 

1. 길이가 1인 모든 문자열은 팰린드롬이니 [0][0], [1][1] ... 은 모두 true로 설정해준다. 

2. 길이가 2인 모든 문자열은 첫번째 글자와 두번째 글짜가 같으면 팰린드롬이니 간단하게 체크해줄 수 있다.

3. 길이가 3이상인 문자열은 str의 길이까지 조사해나가며 체크해준다.

 

총 길이를 저장하는 len 변수보다 큰 수에서 팰린드롬을 발견하면 len에 저장한다.

 

 

이차원 배열이 필요한 이유는 DP로 문제를 풀어야 하기 때문이다 (주륵) 

abcdcba 라는 입력값이 있을 때, 이 문자열 전체가 팰린드롬임을 알기 위해서

1개의 문자열부터 6개의 문자열까지 팰린드롬인 부분을 저장을 해놔야 한다. -> 그것이 바로 DP 

따라서 cdc가 팰린드롬임을 알기 위해서는 2번째 문자 c와 4번째 문자 c가 같다는 조건을 만족시키고, 그 안의 3번째 문자 d가 팰린드롬 조건에 만족되는지 확인해야 한다. 이 사실은 이미 포문을 돌면서 이차원 배열에 저장해두었다. 

예컨대, 이미 3번째 문자 d가 팰린드롬이라는 것을 9번째 줄에서 이미 저장을 해두어 알 수 있다. 

그렇기 때문에 양끝의 문자가 같아도 그 안에 싸인 문자열이 팰린드롬이 아니라면 23번째의 if 문에서 걸러질 수가 있따! 

 

너무 주저리 써놨지만 모두가 이해하길 바라는 마음이다. 안뇽