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

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

코딩테스트 연습 - 가장 긴 팰린드롬

 

풀이방법

문제를 보고 떠오른 해결방법은

abcba가 있다면

abcba -> a / cba

abcba -> ba / ba

abcba -> cba / a

이런 식으로 인덱스를 옮겨가며 좌우를 비교하려는 생각을 했어요

 

좌우 문자가 같으면 현재 길이를 +2를 해주는 식으로 늘려갔어요

 

이런식으로 하는게 틀린건 아닌가봐요

정석은 뭔지궁금하지만...

6개가 틀렷네요

 

다른 풀이로 가기도 애매하고 뭔가될거같은 느낌이였어요 반례를 찾아보자구요 ㅎㅎ

 

글자수가 1개인경우를 체크하지않았네요 

글자수가 1개면 1개가 나와야하는데 저는 습관적으로(?) 길이를 0으로 초기화 해놔서...

최소 1이구요(주어진 문자열은 자연수)!!

수정~~!

 

이제 5개가 틀렸네요...

글자수가 2인경우에도 검사를 안해서 틀리게 나오는 케이스가 있어서

수정해봣는데

그대로네요 테스트케이스로는 안들어가있나봐요 ㅎㅎ...

 

뭘까... 하다가

abccba인경우..!

저의 현재로직으로는 한개의 인덱스로부터 좌우를 비교하기때문에

길이 6이정답인데 1이나오겠죠?

 

양옆의 인덱스부터 검사해주는 로직도 추가를 해줬더니

해결!

 

// 가장 긴 팰린드롬
private func solutionP12904(_ s:String) -> Int {
    let arr: [Character] = s.map { $0 }
    var result = 1
    // 길이가 2인경우 검사케이스
    if arr.count == 2 && arr[0] == arr[1] {
        print(2)
        return 2
    }
    
    // 한개의 인덱스를 기준으로 좌우비교
    for i in 1..<arr.count {
        let fronts: [Character] = arr[0..<i].reversed()
        let ends: [Character] = arr[i+1..<arr.count].map{ $0 }
        
        let minCount = min(fronts.count, ends.count)
        var tempResult = 1
        for j in 0..<minCount{
            let front = fronts[j]
            let end = ends[j]
            
            if front == end {
                tempResult += 2
            } else {
                break
            }
        }
        result = max(result, tempResult)
    }
    // 두개의 인덱스를 기준으로 좌우비교
    for i in 1..<arr.count {
        let fronts: [Character] = arr[0...i].reversed()
        let ends: [Character] = arr[i+1..<arr.count].map{ $0 }
        
        let minCount = min(fronts.count, ends.count)
        var tempResult = 0
        for j in 0..<minCount{
            let front = fronts[j]
            let end = ends[j]
            
            if front == end {
                tempResult += 2
            } else {
                break
            }
        }
        result = max(result, tempResult)
    }
    print(result)
    return result
}
//
//solutionP12904("ABCCBA")
//solutionP12904("abcdcba")
//solutionP12904("abacde")
//
//