[CodeKata] 프로그래머스: 1.23(일), 가장 긴 펠린드롬

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

const isPelindrom =(s) => {
  const cen = Math.ceil(s.length / 2) - 1;
  
  for (let i = 0 ; i <= cen ; i++) {
    if (s[i] !== s[s.length-1-i]) return false;
  }

  return true;
}

const solution = (s) => {
  for (let l = s.length ; l > 1 ; l--) {
    for (let i = 0 ; i <= s.length - l ; i++) {
      if (isPelindrom(s.slice(i,i+l))) return l;
    }
  }
  
  return 1;
}

 

1. isPelindrom() 펠린드롬 판정 함수

• cen 중간 인덱스 변수를 선언한다. 길이가 홀수인 경우 정가운데, 짝수인 경우 가장 가운데 2개 좌표 중 왼쪽 값이 나온다.
• for문을 돌며 양 끝에서 cen까지만 비교하면 된다. i번째와 반대편인 (s.length - 1 - i)번째 값이 다르면 false, 걸리지 않았다면 최종적으로 true를 반환한다.

 

2. solution() 연산 함수

• 가장 긴 길이를 찾아야하므로, 길이 l은 s.length부터 2까지 하나씩 줄어든다. 여기까지 펠린드롬이 없다면 한 글자인 1을 반환한다.
• 다음으로, 시작 인덱스인 i를 잡아준다. 0번째부터, l 길이로 자를 수 있는 마지막 인덱스인 (s.length - l)까지 순회한다.
• s를 i번째부터 l만큼 slice() 한 문자열이 isPelindrom() 일 경우, 펠린드롬을 만족하는 것이므로 길이인 l을 반환한다.

 

🖇 리뷰

풀이들이 나와 대동소이했다. 그러던 중, 나와 사뭇 다르며 정확성 테스트에서 더 빠른 연산시간이 나온 모범답안도 탐색해보고자 가져왔다.

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

* 출처 : 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

• answer는 정답을 누적, len을 s.length, dp는 2차원 배열로 i번째부터 j번째까지 펠린드롬이라면 dp[i][j]를 true로 치환한다.
• 그리고, 자기자신은 펠린드롬이므로 dp[i][i]는 true로 설정한다.
• 그리고, 두 글자가 펠린드롬인 경우가 존재한다면  dp[i][i+1]을 true로 설정하고, answer 역시 2로 갱신한다.
• 그리고, 길이 3부터 len까지의 펠린드롬이 있는지 탐색한다. start는 시작값으로 0부터 중간(len - i)까지, end는 start의 반대편 값이다.
• 만약 s의 start, end 문자가 같다면 내부가 펠린드롬인지 확인한다. dp의 start, end 사이([start+1][end-1])가 펠린드롬이라면 현재 문자열 역시 펠린드롬인 것이다.
• 위 경우에, dp[start][end]도 true로 치환하고, answer는 현재 answer과 i 길이값 중 최대값으로 갱신한다.

 

모범답안 풀이는 불필요한 경우(양쪽 끝의 문자가 다른 경우)에 탐색을 하지 않는다는 장점이 있다. 이를 내 풀이에도 적용할 수 있었다!

const isPelindrom =(s) => {
  if (s[0] !== s[s.length-1]) return false;		// [추가]양 끝 문자가 다른 경우 빠르게 걸러냄!
  
  const cen = Math.ceil(s.length / 2) - 1;
  
  for (let i = 0 ; i <= cen ; i++) {
    if (s[i] !== s[s.length-1-i]) return false;
  }

  return true;
}

대신, 모범답안은 짧은 길이부터 탐색하므로 결국 길이 2부터 s.length까지 전체적으로 탐색해야 한다는 단점이 존재한다.