Palindrome Algorithm 팰린드롬 알고리즘

팰린드롬 알고리즘에 대해서 작성해보려 합니다.

팰린드롬 알고리즘은 면접에서 물어보는 알고리즘으로 유명하기도 합니다.

 

팰린드롬 알고리즘에 대해서 살펴보기 전 팰린드롬의 정의를 찾아보면

팰린드롬은 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열입니다.

(A palindrome is a word, phrase, number or sequence of words that reads the same backward as forward.)

 

팰린드롬의 예로는 기러기, 요기요 등이 있습니다.

그럼 주어진 문자열이 팰린드롬인지 아닌지는 어떻게 확인할 수 있을까요.

 

그냥 뒤집어보면 압니다.

func isPanlindrome(_ s: String) -> Bool {
    if s == String(s.reversed()) {
        return true
    } else {
        return false
    }
}

print(isPanlindrome("기러기"))
// true

뒤집었을 때 원래 문자열이랑 동일한지에 따라서 참 거짓을 판별해주는 isPanlindrome함수가 있습니다.

기러기 문자열은 뒤집었을 때도 동일하게 기러기니까 참이 리턴됩니다.

func isPanlindrome(_ s: String) -> Bool {
    if s == String(s.reversed()) {
        return true
    } else {
        return false
    }
}

print(isPanlindrome("기러가"))
// false

기러가로 문자열을 변경해보겠습니다.

기러가를 뒤집었을 때는 가러기로 읽히고 기러기와 동일하지 않기 때문에 false가 리턴됩니다. 

---

팰린드롬을 확인하는 다른 방법으로는 문자열의 시작 끝부분부터 문자를 비교해나가는 것입니다.

문자열의 길이 / 2 만큼의 비교를 통해서 팰린드롬인지 아닌지 확인할 수 있습니다.

 

아래 기러기를 보면 문자열의 길이가 3입니다.

3/2는 1이고 1번의 비교를 통해서 팰린드롬인지 확인할 수 있습니다.

start인덱스 0, end인덱스 2는 기로 문자가 동일합니다.

문자열의 길이가 홀수이면 러까지 비교를 할 필요가 없습니다.

즉 러를 기준으로 기러기라는 단어로 이루어져 있기 때문입니다.

 

다음은 아래와 같이 기러러기라는 단어가 있습니다.

이 기러러기는 문자열 길이가 4이고 4/2는 2이기 때문에 2번의 비교를 통해서 팰린드롬인지 확인할 수 있습니다.

start인덱스는 0, end인덱스 3은 기로 문자가 동일합니다.

총 2번 비교해야 하기 때문에 각각의 인덱스를 이동해줍니다.

각각의 인덱스를 이동하면 start인덱스는 1, end인덱스 2로 러 문자가 동일합니다.

2번의 비교가 끝났고 기기, 러러로 비교했던 문자가 동일했기 때문에 기러러기라는 단어도 팰린드롬입니다.

 

위 방법을 정리를 해보자면

- 시작과 끝 지점의 인덱스를 시작 지점으로 잡고 문자가 같은지 확인

 

[반복]

- 같다면 start인덱스 + 1, end인덱스 - 1을 해준다.

- 문자가 같은지 확인 (만약 문자열이 다르면 팰린드롬이 아님)

 

- 문자열 / 2 만큼의 비교를 다 끝냈고 문자가 다른 것이 하나도 없었다면 팰린드롬이게 됩니다.

---

*위는 문자 비교의 시작을 인덱스 시작을 양끝에서 중간으로 이동하는 방법으로 작성했으나

인덱스 중간에서 비교를 시작해 인덱스를 끝으로 확장해나가는 방법도 있겠네요.

 

* Leetcode의 문제 131. Palindrome Partitioning이나

5. Longest Palindromic Substring를 풀어보면서 팰린드롬 알고리즘을 응용해봐도 좋을 것 같습니다.

leetcode.com/problems/palindrome-partitioning/

leetcode.com/problems/longest-palindromic-substring/