[Swift] 프로그래머스(Lv3) - 가장 긴 팰린드롬

Kerri·2021년 6월 14일
0

코테

목록 보기
58/67

안녕하세요 !

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

풀이

문자열 s의 길이가 2,500 이하의 자연수이므로 가장 긴 팰린드롬의 길이가 될 수 있는 범위는
1 <= len <= n 입니다. (n은 s의 길이)

  1. 최대 길이가 될 수 있는 n부터 확인해봅니다. (n, n-1, n-2 ...... 1)
  2. left와 end의 index를 구해서 절반을 나눠 같은지 확인합니다.
    이때 end는 left + len - 1 입니다.
    (left = 1이고 len = 3 -> end = 3)
  3. arr[left + i] != arr[end - i] 라면 ok를 false로 해주고 break 합니다.
    arr[left + i] = arr[end - i] 모두 같은 경우는 팰린드롬이므로 len을 return 합니다.
import Foundation

func solution(_ s:String) -> Int {
    let arr = Array(s)
    let n = arr.count
	
    // n, n-1, n-2, .... , 1
    for len in (1...n).reversed() {
        for left in (0...n - len) {
            let end = left + len - 1
            // 팰린드롬인지 아닌지
            var ok = true
                        
            // 절반으로 나눠 검사
            for i in 0..<len/2 {
                if arr[left+i] != arr[end-i] { // 팰린드롬 아님
                    ok = false
                    break
                }
            }
            if ok { // 팰린드롬이라면 
                return len
            }
        }
    }
    
    return 1
}
profile
안녕하세요 !

0개의 댓글