99클럽 코테 스터디 30일차 TIL - 5 Longest Palindromic Substring

5. Longest Palindromic Substring / c++ / Medium / 13분

문제 및 코드

class Solution {
public:
    string longestPalindrome(string s) {
        string answer = "";
        for (int i = 0; i < s.length() && s.length() - i > answer.length(); ++i)
        {
            for (int j = s.length()-1; j >= i; --j)
            {
                if (j - i + 1 <= answer.length()) break;
                if (s[i] == s[j])
                {
                    bool isPalindrome = true;
                    for (int k = 0; i + k <= j - k; ++k)
                    {
                        if (s[i+k] != s[j-k])
                        {
                            isPalindrome = false;
                            break;
                        }
                    }

                    if (isPalindrome)
                    {
                        answer = s.substr(i, j - i + 1);
                    }
                }
            }
        }

        return answer;
    }
};

접근 방식

문자열 / 백트래킹

1. 문자열 s의 부분문자열 중, 길이가 가장 긴 팰린드롬 문자열(거꾸로 뒤집어도 똑같은 문자) 를 반환하는 문제였다.
2. 가장 단순하게 완전 탐색을 시도해보았다.
3. s의 시작부터 i 기준으로 순회한다.
   1. s의 끝부터 j 기준으로 순회한다.
   2. 만약 s[i] == s[j]이면, 첫 글자가 같으므로 팰린드롬일 가능성이 있다.
      1. 여기서 다시 k 를 기준으로 i + k <= j - k 일 때까지 순회한다.
      2. s[i + k] != s[j - k]이면 팰린드롬이 아니므로 isPalindrome을 false로 바꾸고 break
      3. 순회가 끝났는데 isPalindrome 이 true라면 answer를 갱신해준다.

생각해 볼 점

1. 권장이 3시간이어서 걱정했는데 13분 만에 풀려서 허무했다.
2. 역시 가장 쉽고 간편한건 완전 탐색!
3. 풀다보니 계속 최적화 할 수 있는 부분 (탐색하려는 길이가 이미 answer의 길이보다 작거나 같으면 무의미) 이 계속 보여서 추가적으로 넣어줬지만, 결과상 큰 변화는 없었다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL