[프로그래머스] 가장 긴 팰린드롬

https://school.programmers.co.kr/learn/courses/30/lessons/12904#

 

 

---

 

풀이

 

abbc, abcba 인 경우를 잘 살펴보면 

첫번째는 b와 바로 다음 b가 같으므로 펠린드롬 시작,

두번째는 b와 다다음 b가 같아서 펠린드롬이 시작한다.

 

정리하자면 s 왼쪽부터 순회하면서 현재 = 현재의 다음 혹은 현재 = 현재의 다음다음인 경우에만 팰린드롬 가능성이 있는지 확인하면 된다

• s.length-2까지 순회하며 펠린드롬이 가능한 경우를 찾는다
• 현재 = 다음 인 경우 getPalinLen를 구한 뒤 바로 이전의 result와 max 비교
• 현재 = 다음다음 인경우 getPalinLen + 1와 이전의 result비교한다 (1은 중간에 낀 문자)

getPalinLen은 팰린드롬을 시작한 left, right 인덱스를 인자로 받고

left는 왼쪽으로 right은 오른쪽으로 움직이며 서로 대칭이 안 될때까지 움직여서 팰린드롬의 전체 길이를 구한다.

 

주의케이스

입력: "a", 출력: 1

입력: "aa", 출력: 2

 

 

function solution(s) {
    let result = 0;
    if (s.length === 1) return 1;
    
    for (let i = 0; i <= s.length-2; i++) {
        const curr = s[i];
        const next = s[i+1];
        const nextnext = s[i+2];
        
        if (curr === next) {
            const currPalinLen = getPalinLen(i, i+1, s);
            result = Math.max(result, currPalinLen); 
        }
        
        if (curr === nextnext) {
            const currPalinLen = 1 + getPalinLen(i, i+2, s);
            result = Math.max(result, currPalinLen);
        }
    }
    return result;
}

function getPalinLen(left, right, s) {
    let match = 0;
    while(left >= 0 && right < s.length && s[left] === s[right]) {
        match++;
        left--;
        right++;
    }
    return match*2;
}

 

 

18번 틀렸다 뭘까..

 

 

 

입력: "ab" 출력: 1인 경우

즉 최소 palindrome 길이는 1이다

 

최종 코드

function solution(s) {
    let result = 1;
    // if (s.length === 1) return 1;
    
    for (let i = 0; i <= s.length-2; i++) {
        const curr = s[i];
        const next = s[i+1];
        const nextnext = s[i+2];
        
        if (curr === next) {
            const currPalinLen = getPalinLen(i, i+1, s);
            result = Math.max(result, currPalinLen); 
        }
        
        if (curr === nextnext) {
            const currPalinLen = 1 + getPalinLen(i, i+2, s);
            result = Math.max(result, currPalinLen);
        }
    }
    return result;
}

function getPalinLen(left, right, s) {
    let match = 0;
    while(left >= 0 && right < s.length && s[left] === s[right]) {
        match++;
        left--;
        right++;
    }
    return match*2;
}