[Swift] 백준 17609 - 회문

문제 : https://www.acmicpc.net/problem/17609

17609번: 회문

 

첫번째 풀이 (시간초과)

import Foundation

let n = Int(readLine()!)!

for _ in 0..<n {
  var input = readLine()!.map { String($0) }
  var flag = false
  
  if input.reversed() == input { //그 자체로 회문
    print(0)
  } else { //유사 회문
    for i in 0..<input.count {
      let removed = input[i]
      input.remove(at: i)
      if input.reversed() == input {
        print(1)
        flag = true
        break
      }
      input.insert(removed, at: i)
    }

    if !flag { print(2) }
  }
}

- 매번 문자열을 제거했다가 추가하는 방식으로 유사회문을 판단했었는데 찾아보니 reversed()는 O(1)이라서 문제가 안되는데 주어진 문자열의 길이가 10만까지이고 remove, insert가 원소 추가 및 삭제하면서 배열을 재배열하는 과정이 있으니 O(n)이라서, 무려 반복문 안에 반복문 안에 O(n)을 매번 돌렸으니 시간초과가 나는 코드라고 짐작된다.

 

 

두번째 풀이 (투포인터)

- 이번에 이름만 들어봤지 활용은 해보지 않았던 '투포인터' 알고리즘에 대해 찾아보고 적용할 수 있었다.

- 투포인터 알고리즘이란 2개의 점의 위치를 기록하며 처리하는 알고리즘인데, 회문은 처음과 끝에서부터 이동하면서 비교해야하므로 딱 적용하기에 적합하다고 볼 수 있다. 따라서 포인터 하나는 맨 왼쪽, 포인터 하나는 맨 오른쪽에서부터 시작하며 비교한다.

import Foundation

let n = Int(readLine()!)!

//투포인터 알고리즘, 부분 문자열 회문인지 판단 (앞 -> 뒤 <- 이렇게해서 같은지 비교하며 회문판단)
func possiblePalindrome(_ word: [String], _ left: Int, _ right: Int) -> Bool {
  var left = left
  var right = right
  
  while left < right {
    if word[left] != word[right] {
      return false
    }
    left += 1
    right -= 1
  }
  return true
}

for _ in 0..<n {
  var input = readLine()!.map { String($0) }
  var left = 0
  var right = input.count - 1

  if input.reversed() == input { //처음부터 회문이면 0 출력함
    print(0)
  } else { //아니라면 문자 제외했을 때 회문인지 판단해야함
    while left < right {
      if input[left] != input[right] { //양끝 짝이 서로 다르면, 특정 문자 제외 시 범위 내 palindrome인 부분이 있는지를 판단
        if possiblePalindrome(input, left+1, right) || possiblePalindrome(input, left, right-1) { //둘중하나라도 회문이면
          print(1)
          break
        }
        else { //둘다 해당이 안되면 회문이 될 수 없는 알파벳
          print(2)
          break
        }
      } 
      left += 1
      right -= 1
    }
  }
}