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

 

Problem

 

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

---

Solution

 

해당 문제는 완전탐색 문제입니다.

 

모든 경우를 탐색해야 정답을 알 수 있는 문제입니다.

 

하지만 효율적으로 탐색하기 위해 주어진 문자를 긴 문자열에서 짧은 문자열로 잘라서 비교하는게 핵심입니다.

 

1. 초기값 설정

 

인덱스를 찾기 쉽게 문자열을 매핑한 값과 가장 긴 값의 초기값을 설정해줍니다.

 

    //문자열 인덱스를 찾기 쉽게 매핑해줌
    let str:[String] = s.map{String($0)}
    //가장 긴 길이 초기값 설정
    var maxLength:Int = 1

 

2. 이중 for문으로 주어진 문자열을 순회

 

바깥쪽 for문을 0부터 차례대로 

 

안쪽 for문은 반대로 맨 끝 인덱스부터 순회를 해줍니다.

 

for i in 0..<str.count-1 {
        for j in stride(from: str.count-1, to: i+1, by: -1) {

 

3. 문자열의 길이를 설정

 

문자열의 길이는 j-1+1로 고정

 

 var length = j-i+1

 

4. 문자열의 길이가 홀수인지 짝수인지에 따라 중간값 설정

 

만약 문자열이 짝수일 경우 ex) abcefg

 

abc와 efg를 비교해야 하므로 중간값은 c가 됩니다.

 

만약 문자열이 홀수일 경우 ex) abcde

 

ab와 de를 비교해야 하므로 가운데 문자열인 c가 중간값이 됩니다.

 

let middle = length%2 != 0 ? length/2 - 1 : length/2

 

5. 중간값을 기준으로 하나는 처음부터 하나는 끝부터 비교

 

i는 첫번째값 j는 맨 끝 값이므로 여기에 중간값을 더하고 빼서 비교해줍니다.

 

만약 아니라면 length의 값을 변화시켜 알려줍니다.

 for m in 0...middle {
                //왼쪽은 첫번째부터 오른쪽은 마지막부터 비교
                if str[i+m] != str[j-m] {
                    //만약 값이 다르다면 length에 +1을 해서 알려줌
                    length += 1
                    break
                }
            }

 

6. 팰린드롬이라면 가장 긴 문자열의 길이를 갱신

 

length의 길이가 그대로라면 팰린드롬이므로 현재 길이와 maxLength를 비교해서 더 긴 값으로 설정해줍니다.

 

 if length == j-i+1 {
                //가장 긴 길이와 현재 길이를 비교해서 넣어줌
                maxLength = max(maxLength,length)
            }

 

7. 가장 긴 길이를 반환

 

return maxLength

---

Source Code

 

 

---

배운점

 

뒤집은 문자열이 똑같은지를 비교할 때 reversed를 사용했는데 그게 훨씬 비효율적이고

 

또한 비교하기 위해서 ArraySlice[1...n] 등으로 잘라서 비교를 했는데 이런식으로 할 경우

 

훨씬 비효율적이다.

 

하나씩 비교하는게 효율적임.

 

처음부터 끝까지 비교하면 완전 비효율적이겠지? 라고 생각해서 가운데부터 포인터를 두개잡아서 양쪽으로 퍼지면서

 

검사를 하려했는데 오히려 그냥 처음부터 비교해도 됐음.