문제

코드

[ 백트래킹 코드 - 시간초과 ]

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int ans;
void func(int cur, string s, string origin)
{
    if(cur == origin.length())
    {
        string rev = s;
        reverse(rev.begin(), rev.end());
        if(rev == s) ans = max(ans, (int)s.length());
        return;
    }else{
        for(int i=cur;i<origin.length();i++)
        {
            string rev = s;
            reverse(rev.begin(), rev.end());
            if(rev == s) ans = max(ans, (int)s.length());
            func(i+1, s+origin[i], origin);
        }
    }
}
int solution(string s)
{
    func(0, "", s);
    return ans;
}

• 시간초과
  : 문자열 s의 길이가 2500까지라서 엄~~청 크다 --> 터무니없이 실패ㅎㅎ
  (재귀를 이용해 푸는 문제들은 대상인 N이 10만 되도 최대O(2^n) 정도로 급격히 커짐)

---

[ 유효성 검사 실패 ]

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
bool ch[2501];
int solution(string s)
{
    int ans=1;
    for(int i=0;i<s.length();i++)
    {
        /* 답이 홀수인 경우 검사 */
        int endsize = min((int)((s.length()-1) - i), i);
        for(int size=endsize;size>=1;size--)
        {
            string tmp = s.substr(i-size,size*2+1);
            string rev = tmp;
            reverse(rev.begin(), rev.end());
            if(rev == tmp) {
                ans = max(ans, (int)tmp.length());
                break;
            }
        }
        /* 답이 짝수인 경우 검사 */
        int lastsize = (s.length()-1) - i;
        for(int size=lastsize;size>=1;size--)
        {
            string tmp = s.substr(i,size+1);
            string rev = tmp;
            reverse(rev.begin(), rev.end());
            if(rev == tmp) {
                ans = max(ans, (int)tmp.length());
                break;
            }
        }
    }
    return ans;
}

• 접근
  정답이 짝수일때와 홀수일 때 다르게 검사 해야한다는 것을 느껴서 나눔
  --> 이렇게 푸는 풀이도 있지만 아래에 있는 풀이가 더 깔끔함
• 유효성 검사
  : 유효성 검사 1번에서 계속 막힘 - 시간초과
  (줄이려고 substr, reverse줄인다고 줄였으나 실패..)
  substr() -> 문자를 자르고 복사하는 과정 -> O(N)
reverse() -> 문자를 그 자리에서 역순으로 뒤집음 -> O(N)

---

[ 정답코드 ]

#include <iostream>
#include <string>
#include <algorithm>
#include <stack>
using namespace std;
int solution(string s)
{
    int len=s.length();
    while(len>=2)
    {
        for(int i=0;i<=s.length()-len;i++)
        {
            int left = i;
            int right = i+len-1;
            bool flag = false;
            while(left <= right)
            {
                if(s[left] != s[right]) {
                    flag = true;
                    break;
                }
                left++;
                right--;
            }
            if(flag) continue;
            return len;
        }
        len--;
    }
    return 1;
}

• 핵심
  1) 긴 문자열부터 검사해서 찾으면 바로 return 해야 함
  (이렇게 안하면 유효성 통과X)
  2) left / right 변수로 양옆에서 인덱스로 검사하여 짝수 / 홀수 경우를 나누지 않아도 됨
  (길이가 짝수이든 홀수이든 같은 로직으로 실행가능)

• 느낀 점
  : 종종 문자열에서 특정 패턴을 찾는 문제에서 left/right나 front/back으로 양옆에서 접근하는 방식으로 빠르게 문제를 푸는 문제들이 있는것 같다.(기억하자)

• 참고 글
  https://kosaf04pyh.tistory.com/185