프로그래머스 - 연습 문제 - 가장 긴 팬린드롬

가장 긴 팰린드롬

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

프로그래머스

문제 설명

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다.
문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 "abcdcba"이면 7을 return하고 "abacde"이면 3을 return합니다.

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

---

입출력 예sanswer

"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

 

---

[풀이 설명]

 

일단 효율성 st, end의 포인터를 둬서 문제를 풀었는데 효율성을 통과히지 못했다.

 

[틀린 코드]

 

function solution(s)
{
    var answer = 0;
    
    var st = 0;
    var ed = s.length - 1;
    var tmp = 0;
    var firstFront = true;
    while (true) {
        tmp++;
        console.log(st, ed)
        if (s[st] === s[ed]) {
            var cnt = 0;
            while(true) {
                st++;
                ed--;
                cnt += 2;
                if (s[st] !== s[ed]) break;
                if (st === ed) {
                    cnt++;
                    answer = Math.max(answer, cnt);
                    break;
                }
                if (st > ed) {
                    answer = Math.max(answer, cnt);
                    break;
                }
            }
        }
        else if (firstFront) {
            st++;
            if (st === ed) {
                firstFront = false;
                st = 0;
            }
        } 
        else if (!firstFront) {
            ed--;
            if (st === ed) break;
        }
        if (tmp === 10) break;
        if (st === ed) break;
    }

    return answer;
}

console.log(solution("abacde"))

 

그래서 구글링 중에 좋은 문제 풀이가 있어서 머리에 기억하고 싶은 마음에 이렇게 정리하는 글을 올린다.

출처: https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EA%B0%80%EC%9E%A5-%EA%B8%B4-%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-JS

 

<생각 원리>

 

1. 근본적으로 문자하나는 팬린드롬임... => answer = 1

2. 문자 2개가 팬린드롬이 되는 경우는 aa, bb, cc, ... 이런 경우임. 

이 부분을 선제적으로 고려해주는게 문제 풀이하는데 쉬움.. 이건 대충 틀린 방법으로 문제를 풀다보면 느낌적으로 알 수 있어서 설명하기가 어려운데..지금 문제를 풀 때 문자하나 즉 자기자신이 팬린드롬이라는걸 체크해주고 시작할건데.

마찬가지로 코드의 풀이의 쉬움을 위해 2개의 문자의 팬린드롬의 경우도 그렇게 해준다고 생각하면된다.

 

let answer = 1;  // 가장 긴 팰린드롬의 길이를 저장할 변수 (문자열은 최소 1의 길이를 가지므로 default를 1로 초기화)

// 자기자신은 곧 팰린드롬이다
for(let i = 0; i < len; i++) {
  dp[i][i] = true;
}

// 길이가 2인 팰린드롬이 있는지 검사한다
// 판단조건은 s[i] == s[i+1]이 일치하면 
// 길이가 2인 팰린드롬이 성립한다.
// 성립할 경우 answer도 2로 갱신한다.
// dp[i][i+1]의 범위를 탐색하므로
// 반복문을 0부터 len-1 까지 하는것에 주의하자.
for(let i = 0; i < len - 1; i++) {
  if(s[i] === s[i+1]) {
    answer = 2;
    dp[i][i+1] = true;
  }
}

3. 결론적으로 우리는 아래와 같이 고려해주면 된다.

• 시작문자가 start 이고 종료문자가 end 일때 (left, right 처럼 팬린드롬인지 판단함.)
• 첫번째 조건: s[start] === s[end] 로 나태낼 수 있다. ( 같은 문자면 팬린드롬인가? 하는거지)
• 세번째 조건: dp[start+1][end-1] 로 나타낼 수 있다. (dp로 확인해서 start ~ end 안이 이미 true 즉 => 팬린드롬이라고 설정 되있다면 당연히 팬린드롬인것.)

이런식인것.

 

// 길이가 3인 팰린드롬이 있는지 검사할 것이다 => 문자 한개, 두개는 이미 고려함
// 최대 팰린드롬 길이는 주어진 문자열과 동일할 수 있기에
// len과 일치할 때 까지 반복문을 돌린다는 것을 주의하자
for(let i = 3; i <= len; i++) {
  // 시작문자는 항상 0부터 시작할 것이다.
  // 시작문자가 가질 수 있는 최대 index값은 len - i와 같다.
  // 이는 현재 팰린드롬의 길이가 i인 상황이기 때문에
  // 이 길이보다 짧아지는 index는 필요없기 때문이다.
  for(let start = 0; start <= len-i; start++) {
    // 종료문자의 index는 시작문자 index + 현재 팰린드롬 길이 i - 1 이다.
    // 즉 i 크기만큼 떨어져있는 곳의 index이다.
    const end = start + i - 1;
    if(s[start] === s[end] && dp[start+1][end-1]) {
      dp[start][end] = true;
      // answer 의 값은 항상 최대값으로 갱신되어야 한다.
      answer = Math.max(answer, i);
    }
  }
}

---

 

[전체 코드]

 

function solution(s) {
    var answer = 1;
    const length = s.length;
    const dp = new Array(length).fill().map(_ => new Array(length).fill(false));
    
    for(let i = 0; i < length; i++) {
        dp[i][i] = true;
    }
    
    for(let i = 0; i < length - 1; i++) {
        if(s[i] === s[i + 1]) {
            dp[i][i + 1] = true;
            answer = 2;
        }
    }
    
    for(let i = 3; i <= length; i++) {
        for(let st = 0; st <= length - i; st++) {
            const ed = st + i - 1;
            if(s[st] === s[ed] && dp[st + 1][ed - 1]){
                dp[st][ed] = true;
                answer = Math.max(answer, i);
            }
        }
    }
  
    return answer;
}

 

 

---

후기

 

머리로는 이해가 됬다 하는데

설명하기가 어렵다.

뭔가 내가 제대로 이해하지 못한것이 있나?

나중에 까먹을때즘 다시 풀면 알겠지.

일단은 정리해보았다.

참고로 dp의 이용은 점화식의 식의 완성으로

식이 완성된다기 보다 이게 지금 팬린드롬인지? 확인하는거에 가깝다.

팩토리알 재귀를 dp로 최적화할 때 하는 방법이랑 맥락이 유사하다고 할 수 있겠다.