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

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

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

안녕하세요 후르륵짭짭 입니다.

이번에도 그냥 평범한 문제를 들고왔습니다.

그냥 감을 키우기 위해서 가져왔고요.

쪼금 생각했는데, 밑의 예시를 통해서 해답을 얻었습니다.

 

** 풀이 방법 **

저의 풀이 방법은 재귀 방식으로 풀었습니다.

처음에는 가장 긴 길이 부터 검사해서 하나씩 팰린드롬인지 아닌지 탐색을 할까?

생각을 했는데,,, 이러면 3중 포문을 돌려야 해서 시간 초과 날 것 같은 두려움에,,,, 다른 방법을 생각했습니다.

그래서 생각한게, 기준점으로 부터 점점 넓혀 가는 방식으로 생각 했습니다.

위의 그림을 보면 좌우로 하나씩 넓혀 가는 것을 볼 수 있습니다.

따라서 아래 처럼 코드를 작성 했습니다.

func solution(_ s:String) -> Int {
    
    let s_list = s.map { (char) -> String in
        return String(char)
    }
    
    var maxValue = 0
    
    for (index , element) in s_list.enumerated(){
        
        if index + 1 < s_list.count && element == s_list[index + 1]{
            
            maxValue = max( makeString(index, index, 0, s_list) * 2 + 1, makeString(index, index + 1, 0, s_list) * 2 + 2, maxValue )
        
            
        }
        else{
            
           maxValue = max(  makeString(index, index, 0, s_list) * 2 + 1, maxValue )
        }
        
        print(index , maxValue)
        
    }
    
    return maxValue
}

func makeString(_ lhsIndex : Int ,_ rhsIndex : Int,_ cnt : Int ,_ list : [String]) -> Int{
    
    if lhsIndex - 1 < 0 || rhsIndex + 1 >= list.count {return cnt}
    
    if list[lhsIndex - 1] == list[rhsIndex + 1] {
        return makeString(lhsIndex - 1, rhsIndex + 1, cnt + 1, list)
    }
    
    return cnt
}

그래서 만약에 그림의 첫번 째 방법과 같다면 반환 된 cnt * 2 를 해주고 1을 더해줬고

두번 째 그림과 같다면 cnt * 2 에 2를 더해준 다음 최대값을 찾았습니다.

 

** 다른 사람의 풀이 방법 **

func solution(_ s:String) -> Int {
    let arr: [Character] = Array(s)
    var answer = 0

    for i in 0..<arr.count {
        for j in stride(from: arr.count - i, to: answer, by: -1) {
            var left = i
            var right = i + j - 1
            while left <= right, arr[left] == arr[right] {
                left += 1
                right -= 1
            }

            if left > right { answer = max(answer, j) }
        }
    }

    return answer
}

이 분 같은 경우는 최대 길이로 부터 하나씩 탐색해 가는 방식을 생각한 것 같습니다.

처음에는 이런 방법을 생각했지만,, 시간 초과 날 것 같아서 안 했는데, 가능했나 봅니다.