[Algorithm] 가장 긴 펠린드롬

[hwangJi-dev]

💬 문제

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

💬 Idea

• 가장 긴 펠린드롬의 길이를 구하는 문제이므로 가장 큰 개수 (s의 count)부터 -1씩 내려가면서 최고 길이를 구한다.
• j : 시작점
• p : 중간 인덱스
• l : 끝 인덱스
• j부터 p까지 돌면서 양 끝 인덱스를 비교하고, 비교군은 k씩 좁혀간다.
  • abba
    • 4인 펠린드롬을 구할 때 → a와 a 비교 (0, 3) // b와 b 비교 (1, 2)
    • 3인 펠린드롬을 구할 때
      • abb → a와 b 비교
      • bba → b와 a 비교

💬 풀이

import Foundation

func solution(_ s:String) -> Int {
 var maxSubstring = 1
 var s = Array(s)
 
 if s.count == 0 { return 0 }
 if s.count == 1 { return 1 }
 
 for i in stride(from: s.count, to: 1, by: -1) {
 var isPal = false
 
 ol: for j in 0...s.count - i {
 var p = (i / 2) + j
 var l = j + i - 1
 
 for k in j...p {
 if s[k] != s[l - (k - j)] {
 continue ol
 }
 }
 
 return i
 }
 }
 
 return maxSubstring
}