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

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

프로그래머스

 

2023.07.26 기준 Level 3

 

알고리즘 공부를 위해 풀고 기록하는 글입니다!
참고만 해주시고 더 좋은 풀이법이 있다면 알려주세요!

 

아이디어

앞뒤를 뒤집어도 똑같은 문자열인 팰린드롬을 찾는 문제였습니다.

 

주어진 문자열 s의 부분 문자열(Substring)에서 가장 긴 팰린드롬의 길이를 return하면 됩니다.

문제 자체는 매우 단순합니다.

 

s를 탐색하며 substring을 구하고 팰린드롬인지 체크하면 됩니다.

가능한 최대 길이는 s의 길이부터 1까지입니다.

 

우리는 최대 길이를 구해야하기 때문에 length를 s.count부터 1까지 줄여가면서 해당 length만큼의 substring을 구하고 이 substring이 팰린드롬인지 확인하면 됩니다.

 

풀이

첫 번째 풀이 (시간 초과)

fileprivate func solution(_ s:String) -> Int {
    let s = Array(s)
    
    for length in stride(from: s.count, to: 0, by: -1) {
        
        var startIndex = 0
        
        while startIndex+length-1 < s.count {
            let endIndex = startIndex + length - 1
            let subArr = Array(s[startIndex...endIndex])
            if subArr == Array(subArr.reversed()) {
                return length
            }
            
            startIndex += 1
        }
    }

    return 0
}

생각나는 아이디어대로 곧바로 구현한 풀이였습니다.

하지만 효율성 테스트에서 시간 초과가 발생했습니다.

 

startIndex와 여기에 length-1을 더한 endIndex사이의 SubSequence를 구하고 이것을 reversed()한 어레이와 같은지 비교해서 

같다면 팰린드롬이기 때문에 이 때의 length를 리턴하는 로직입니다.

 

로직 자체는 문제가 없지만 실행 시간을 높이고 있는 코드가 있었습니다.

바로 Array(s[startIndex...endIndex]) 부분입니다.

SubSequence를 == 연산자 사용을 위해 어레이로 타입 변환하는 코드입니다.

 

 

플레이그라운드에서 테스트를 해보니 SubSequence를 구하는 arr[300...9000000]의 실행 시간이 3초 이상 소요되었습니다.

또한 Array(subArray)역시 3초 이상 소요되었습니다.

즉, 서브시퀀스를 구하고 이를 어레이로 변환하는 과정에서 시간이 많이 소요되어 효율성 테스트에서 실패한 것으로 보입니다.

두 작업 모두 O(N)으로 예상됩니다.

 

 

두 번째 풀이 (통과)

fileprivate func solution(_ s:String) -> Int {
    let s = Array(s)
    
    for length in stride(from: s.count, to: 0, by: -1) {
        outer: for startIndex in 0...s.count-length {
            var start = startIndex
            var end = startIndex + length - 1
            
            // 팰린드롬인지 확인
            while start < end {
                if s[start] != s[end] {
                    continue outer
                }
                start += 1
                end -= 1
            }
            
            return length
        }
    }

    return 0
}

첫 번째 풀이에서 시간 초과가 발생한 부분을 제거하고 직접 인덱스로 비교하는 방식을 사용했습니다. (슬라이딩 윈도우 알고리즘)

 

기본적으로 length를 s.count부터 1씩 줄여가며 비교하는 것은 동일합니다.

start와 end로 부분 문자열의 범위를 정하고 각각 1씩 증가, 감소 시키며 팰린드롬인지 비교합니다.

 

s[start]와 s[end]가 다르다면 팰린드롬이 아니기 때문에 곧바로 continue시켜 다음 작업을 진행합니다.

팰린드롬이 맞다면 정답을 구한 것이기 때문에 length를 return합니다.

 

 

 

마무리

예상하지 못한 곳에서 시간 초과가 발생하여 원인을 찾는데 시간이 조금 걸렸습니다.

그래도 이번 기회로 어레이를 다룰 때의 시간 복잡도에 대해 다시 한번 경각심을 가질 수 있었습니다.

가능한 경우에는 인덱스를 활용하여 원본 어레이에 직접 접근하는 것이 좋고 SubSequnce와 에러이로의 타입 캐스팅은 최소화 하는 것이 좋을 것 같습니다.