[일일코테 Special1] 가장 긴 팰린드룸 - 프로그래머스(레벨3)

문제

programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬

코딩테스트 단톡방에서 누군가 질문을 올렸길래 나도 해봤다. 대충 풀이 방법을 끄적이다가 노트에 적어가면서 풀었는데. 대략적인 접근 방법은 금방 떠올렸지만 상세한 구현 세부사항 하나하나에서 부딧히면서 시간을 무려 4시간이나 끌었던 문제다.

 

너무 어렵다.. 어떻게 하지..

 

일단 잊어버리지 않게 글 생성만 해놓고 나중에 차근차근 정리해야겠다.

대략적으로 끄적여본 노트. 그림을 그려보니 몇 가지 패턴을 발견했고, 한번 계산한걸 어딘가에 저장하지 않고도 건너띌 수 있는 방법을 발견했다.

중복 코드도 많고 동일한 일을 함수도 많은데. 아래 최종 코드는 다시 정리를 좀 해봤다. 그래도 다른 사람들이 만든 코드가 더 깔끔하더라.. 어쨋든 성공한것 자체에 만족.

코드

function lengthOfPalindrome(p, s, e) {
    const size = e - s;
    const left = Math.floor((size-1) /2) + s; 
    const right = Math.floor(size / 2) + s;
    
    let length = 0;
    for(let i=0; (i < size/2) && p[left-i] == p[right+i]; ++i) {
        if ((left -i) == (right + i)) {
            length += 1;    
        } else {
            length += 2;
        }
    }
    return length;
}

function findSize(p, s, e, parentLength, left)  
{
    const size = e - s;
    if (size <= parentLength) {
        return parentLength;
    }
    
    const myLength = lengthOfPalindrome(p, s, e);
    const maxLength = Math.max(myLength, parentLength);
    
    if (left) {
        return findSize(p, s, e - 1, maxLength, true);
    } else {
        return findSize(p, s + 1, e, maxLength, false);
    }
}

function solution(s)
{
    const c = lengthOfPalindrome(s, 0, s.length);
    const l = findSize(s, 0, s.length - 1, c, true);
    const r = findSize(s, 1, s.length, c, false);
    return Math.max(l, c, r);
}