longest palindrome

문제: https://leetcode.com/problems/longest-palindromic-substring/

주어진 문자열 중 가장 긴 펠린드롬을 구하는 문제

처음 문제 풀때 시간초과 때문에 고생했다. 하지만 leetcode에서 힌트를 본 뒤에 생각해낸 문제.
풀이를 알고있는 지금은 나름? 간단한 문제라고 생각한다.

문제해결의 point!

• 펠린드롬이란 중심점을 기준으로 양옆이 같으면 펠린드롬이다.
  ex) 'a' - 펠린드롬 , 'bab' - 펠린드롬 , 'xbabx' - 펠린드롬
• 펠린드롬은 홀수 개수 일 수도 있고 짝수 개수 일 수도 있다.

위의 2가지의 힌트를 보셨다면 먼저 다시 문제를 고민하는걸 추천할게요!

해결방법

1. 인자로 받은 s를 처음부터 끝까지 순회한다. (i인덱스로)

2. 펠린드롬의 중심을 짝수, 홀수로 하기 위해 for문을 0~1까지 한번더 돌아준다. (j인덱스)
   ex) abbd 의 경우 중심점이 b -> abb 로 검사하고 bb -> abbd 이렇게 2가지 경우를 검사해줘야한다.

3. lt=i - left , rt=i+j - right 로 각각의 기준점의 left,right를 정해준다.

4. while문에서 s[lt]&& s[lt]===s[rt] (lt가 음수가 되면 에러가 난다. rt는 undefined가 된다.) 조건으로 lt,rt를 업데이트해준다.

5. 위의 구한 값으로 s를 slice해서 answer와 비교해 answer를 업데이트한다.

6. 위의 과정을 반복

code

const longestPalindrome = (s) => {
  let answer = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = 0; j < 2; j++) {
      let lt = i;
      let rt = i + j;
      while (s[lt] && s[lt] === s[rt]) {
        lt--;
        rt++;
      }
      const tmpStr = s.slice(lt + 1, rt);
      if (tmpStr.length > answer.length) answer = tmpStr;
    }
  }
  return answer;
};

마무리

힌트를 보고도 바로 위의 코드처럼 깔끔하게 구현할 수 없었다. leetcode의 장점은 다른 사람의 힌트를 볼 수 있는 것인데 어떤 분이 깔끔하게 정리해 놓으신 코드를 보고 내 로직과 같아서 좀 수정했다.

이런 문제는 아느냐 모르느냐에 따라서 난이도가 차원이 달라지는 것 같다. (사실 모든 알고리즘 문제가 그럴것 같긴하지만..ㅋ) 결국 많은 문제를 풀어야 한다. 몰아서 하는 것보다는 꾸준하게 하자.