647. Palindromic Substrings
https://leetcode.com/problems/palindromic-substrings
문제
유명한 Palindromic문제를 좀 더 어렵게 만든 문제이다. 팰린드롬이란 aba처럼 거꾸로 읽어도, 똑바로 읽어도 똑같은 문자열을 말한다. 하지만 이 문제는 연속적인 순서안에서 팰린드롬 문자열 개수를 구하는 문제이다. Example 1을 보면 연속적인 순서에 따라서 나올수 있는 문자열은 "a", "b", "c", "ab", "bc", "abc"가 된다. 그 중에서 팰린드롬인 문자열을 찾으면 "a", "b", "c" 즉 3개이기 때문에 3을 리턴해주면 된다.
풀이(Brute Force 처음 풀었던 방식)
가장 직관적으로 생각하고 구현한 코드이다. for문 2개를 사용하였고 tmp에는 똑바로된 문자열 rtmp에는 거꾸로된 문자열을 저장하고 비교한다. 일치하면 증가하여 리턴하는 문제이다.
풀이(DFS 방식)
문자열 "acbca"가 있을 때 똑바로 된 문자열 "acbca"와 거꾸로 된 문자열 "acbca"를 비교하는 것 말고
1. 맨 앞 문자 "a"와 맨 뒤 문자 "a"를 비교하고 맞으면 한 칸씩 앞당겨 다음 문자를 비교한다.
2. "c와" "c를 비교하고 맞으면 한 칸씩 앞당겨 다음 문자를 비교한다.
3. 만약 왼쪽 인덱스, 오른쪽 인덱스가 같거나 뒤바뀌면 이것은 팰린드롬이다.
라는 방법으로 구현한 것이다.
또한 중첩 포문일 때 (0,0) (0,1) (0,2) (1,1) (1,2) (2,2) 이런식으로 주로 알고 있었지만 이렇게 할 경우 캐시에서 리턴되는 값이 적어지므로 오래 걸린다.
(0,0) (1,1) (2,2) (0,1) (1,2) (0,2) 이렇게 호출하면 캐시에서 리턴되는 값이 많아지므로 적게 걸리게 된다.
풀이(DP 방식)
Example "abcba"
해당 테이블은 DP표이다. 색깔은 for문 도는 순서를 나타낸 것이다.(빨간색 처음 ~ 보라색 마지막)
즉 길이가 1일 때부터 길이가 5일 때까지 분할정복하여 구현하였다. 길이가 1일 때는 당연히 팔린드롬이므로 1일 것이고 길이가 2일 때에 s[j] == s[j+i]를 확인한다. 보면 같지 않으므로 0으로 둔다. 길이가 3일 때를 확인해보면 "bcb"에서 s[j] == s[j+i] => b == b이므로 이 안쪽이 팔린드롬인지 확인해야 한다. 즉 "c"는 팔린드롬이므로 1인 것이다.
이런식으로 길이가 5일 때를 확인해보면 s[j] == s[j+i] => a == a이고 dp[1][3]을 확인해야 한다.("bcb" 확인) dp[1][3]은 팔린드롬이므로 "abcba"는 팔린드롬인 것이다.
결과
풀이(DFS 방식)
풀이(DP 방식)
배운점
- 재귀함수 호출 할 때 필요없는 연산을 줄이기 위해 캐시를 사용해야 한다.
- 캐시값을 최대한 받아 올 수 있도록 구현해야 한다.
