[백준 10987] 모음의 개수 (Swift)

[백준 10987] 모음의 개수 (Swift)

10987번: 모음의 개수

입력 문자열에서 모음(a, e, i, o, u)의 갯수를 세서 출력하는 단순한 문제이다.

풀이를 어떻게 할지 고민하다가 두 가지 방법을 생각해 보았다.

1. 문자열의 문자를 돌며 어떤 문자가 a, e, i, o, u 중 하나라도 같은지 확인하기 (== 연산자 활용)
2. a, e, i, o, u 를 담은 모음 배열을 만들고, 문자열의 문자를 돌며 어떤 문자가 모음 배열에 포함되는지 확인하기 (contains(_:) 활용)

두 풀이를 모두 작성했고 둘 다 모두 잘 풀렸다.

개인적으로 의문이 생겼던 부분은 두 풀이의 실행시간이 완전히 같았다는 것이다.

나는 당연히 풀이1이 더 빠를 것이라 예상하고 풀이1을 먼저 시도하고, 맞은 걸 확인한 뒤 풀이2도 시도했는데 실행시간이 같아서 놀랐다.

그래서 둘의 실행시간을 자세히 탐구해 보았다.

풀이 1 (== 연산자 활용)

let input = readLine()!
var answer = 0
for char in input {
    if char == "a" || char == "e" || char == "i" || char == "o" || char == "u" {
        answer += 1
    }
}
print(answer)

풀이1에서 문자열의 길이가 k라면, 비교해야 할 모음의 개수는 5개이기 때문에 최악의 경우 실행시간은 k*5가 된다.

하지만 내가 풀이1이 더 빠를 거라고 예상했던 이유는 contains(_:) 의 시간복잡도가 O(n) 이고, 따라서 당연히 이보다는 == 연산자가 빠를 거라고 생각했기 때문이다.

풀이1에서는 == 연산을 || 로 이어서 다섯 번 사용하긴 하지만, || 연산의 특성상 맨 왼쪽부터 시행해 하나라도 true이면 전체 결과도 true이므로 더 이상 비교하지 않기 때문이다. 이걸 short-circuit evaluation 라고 한다고 한다. (참고 : Swift 공식 문서)

그래서 조건문 (char == "a" || char == "e" || char == "i" || char == "o" || char == "u") 을 끝까지 확인해야하는 경우만 아니라면, k*5보다는 빠른 실행시간을 가질 것이라 예상할 수 있다.

풀이 2 (contains(_:) 활용)

let input = readLine()!
let aeiou: [Character] = ["a", "e", "i", "o", "u"]
var answer = 0
for char in input {
    if aeiou.contains(char) {
        answer += 1
    }
}
print(answer)

풀이2에서 사용하는 contains(_:) 의 시간복잡도가 O(n) 이다. 이때 n은 배열의 길이이며, 여기서는 aeiou 의 길이인 5가 된다.

문자열의 문자를 돌며 contains를 적용하기 때문에, 문자열의 길이가 k일 때 실행시간은 k * 5이다.

이 때 내가 간과한 것은 contains의 동작이다.

공식문서에는 contains(_:) 의 시간복잡도가 O(n)이라고만 설명되어 있다.

하지만 contains 역시 배열의 앞 요소부터 하나씩 비교하므로, 탐색할 요소가 앞에 있는 경우 n보다 빠르게 결과값을 반환한다.

단순화해 표현하자면 [0, 0, 0, 0, 1]에서 contains(1)로 1을 찾는 것보다 [1, 0, 0, 0, 0]에서 contains(1)로 1을 찾는 것이 더 빠르다는 것이다. 찾는 요소가 맨 앞에 있기 때문이다.

(자세한 내용은 contains(_:) 문서와 함께 해석한 이 글에 설명되어 있다)

결론

== 를 사용하는 풀이1은, 최악의 경우 조건문 (char == "a" || char == "e" || char == "i" || char == "o" || char == "u") 을 전부 비교해야 하지만, 앞의 조건문이 하나라도 true인 경우 short-circuit evaluation에 의해 나머지 조건문은 실행되지 않는다.

contains(_:)를 사용하는 풀이2 역시, 최악의 경우 모음 배열의 끝까지 요소가 포함되는지 비교해야 하지만, 찾는 요소가 앞쪽에 있는 경우 나머지 비교를 멈추고 즉시 true를 반환한다.

그렇기 때문에 조건문 비교 순서(char == "a" || char == "e" || char == "i" || char == "o" || char == "u") 와 contains를 확인하는 배열의 요소 순서(["a", "e", "i", "o", "u"])가 같은 한 둘은 동일한 시간복잡도를 가지는 것이다!