백준 10988번 문제 풀이

문제

https://www.acmicpc.net/problem/1032

제출 코드

let input = readLine()!
var result: Bool = true
for index in 0..<(input.count/2) {
	let leadingIndex = input.index(input.startIndex, offsetBy: index)
	let trailingIndex = input.index(input.endIndex, offsetBy: -index-1)
	if input[leadingIndex] != input[trailingIndex] {
		result = false
		break
	}
}
print(result ? 1 : 0)

개선 코드

let input = readLine()!
var result: Bool = true
var leadingIndex = input.startIndex
var trailingIndex = input.index(before: input.endIndex)
for _ in 0..<(input.count/2) {
    if input[leadingIndex] != input[trailingIndex] {
        result = false
        break
    }
    leadingIndex = input.index(after: leadingIndex)
    trailingIndex = input.index(before: trailingIndex)
}
print(result ? 1 : 0)

개선된 점

1. 인덱스 순회로 인한 시간 복잡도 개선
   • 개선 전
     • 반복문 내 index(_:offsetBy:) 호출 → offset 만큼의 순회로 인한 시간 복잡도 증가 → 최악의 경우 O(n2)
   • 개선 후
     • 반복문 호출 전 인덱스 초기화 및 반복문을 통해 인덱스 값 변경
   • 문자열 길이가 길수록 시간복잡도가 제곱으로 증가할 수 있는 것을 방지함으로써 성능이 개선되었습니다.
   • 불필요한 반복 호출 및 초기화를 위한 연산을 제거하여 오버헤드 발생 가능성이 개선되었습니다.