회문(Palindrome)

회문은 앞으로 읽으나 뒤로 읽으나 동일한 단어나 구문을 말한다. 회문은 소문자나 대문자를 허용하며, 공백, 구두점, 단어 구분자를 포함할 수 있다.

회문을 확인하는 알고리즘은 프로그래밍 면접에서 자주 등장하는 질문 중 하나다.

예제

'racecar'는 앞뒤로 똑같이 읽히는 회문(palindrome)의 유효한 예시이다. 아래 예제는 racecar가 회문으로 인정되는 다양한 사례를 보여준다.

raceCar
r a c e c a r
r?a?c?e?c?a?r?
RACEcar

알고리즘

회문(palindrome)을 확인하기 위해 문자열의 문자를 처음과 끝에서부터 비교한다. 비교하면서 문자열의 중앙으로 이동하며, 양쪽에서 동일한 거리를 유지한다. 이 회문 알고리즘 구현에서는 재귀를 사용해 왼쪽과 오른쪽의 문자를 하나씩 비교하며 중앙으로 이동한다.

코드 설명

Swift로 구현한 재귀적 팰린드롬 검사 코드는 다음과 같다:

func isPalindrome(_ str: String) -> Bool {
  let strippedString = str.replacingOccurrences(of: "\\W", with: "", options: .regularExpression, range: nil)
  let length = strippedString.count

  if length > 1 {
    return palindrome(strippedString.lowercased(), left: 0, right: length - 1)
  }

  return false
}

private func palindrome(_ str: String, left: Int, right: Int) -> Bool {
  if left >= right {
    return true
  }

  let lhs = str[str.index(str.startIndex, offsetBy: left)]
  let rhs = str[str.index(str.startIndex, offsetBy: right)]

  if lhs != rhs {
    return false
  }

  return palindrome(str, left: left + 1, right: right - 1)
}

이 알고리즘은 두 단계로 진행된다.

첫 번째 단계에서는 팰린드롬을 검사할 문자열을 isPalindrome 메서드에 전달한다. 이 메서드는 먼저 정규식을 사용해 단어가 아닌 문자를 제거한다. \W는 정규식에서 단어가 아닌 문자를 의미하며, 문자열 리터럴에서 역슬래시를 이스케이프하기 위해 두 개의 역슬래시를 사용한다.

let strippedString = str.replacingOccurrences(of: "\\W", with: "", options: .regularExpression, range: nil)

그 후 문자열의 길이를 확인해 단어가 아닌 문자를 제거한 후에도 유효한 길이인지 검사한다. 이 문자열은 소문자로 변환된 후 다음 단계로 전달된다.

두 번째 단계에서는 문자열을 재귀 메서드에 전달한다. 이 메서드는 문자열과 왼쪽, 오른쪽 인덱스를 받는다. 메서드는 인덱스를 사용해 문자열의 양쪽 문자를 비교한다. 왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같으면 전체 문자열을 검사했고, false를 반환하지 않았으므로 문자열이 양쪽에서 동일하며 true를 반환한다.

if left >= right {
  return true
}

이 검사가 통과하지 않으면 지정된 인덱스의 문자를 가져와 비교한다. 만약 두 문자가 다르면 메서드는 false를 반환하고 종료한다.

let lhs = str[str.index(str.startIndex, offsetBy: left)]
let rhs = str[str.index(str.startIndex, offsetBy: right)]

if lhs != rhs {
  return false
}

두 문자가 같으면 메서드는 자신을 다시 호출하고 인덱스를 업데이트해 나머지 문자열을 계속 검사한다.

return palindrome(str, left: left + 1, right: right - 1)

단계별 예시:

1단계:
race?C ar -> raceCar -> racecar

2단계:

|     |
racecar -> r == r

 |   |
racecar -> a == a

  | |
racecar -> c == c

   |
racecar -> 왼쪽 인덱스 == 오른쪽 인덱스 -> true 반환

추가 자료

회문 위키백과

작성자: Joshua Alvarado