[프로그래머스] 짝지어 제거하기 Swift

프로그래머스 - 짝지어 제거하기

나의 풀이

처음엔 시간복잡도 n^2으로 풀었는데 문자열 길이기 1,000,000이하라 당연히 효율성에서 시간초과.
스택으로 풀었더니 깔끔하게 해결 ... 은 아니지만 stack.count > cnt - i 을 해줘서 그나마 효율성 통과했다.

import Foundation

func solution(_ s:String) -> Int{
    if s.count % 2 != 0{ // 홀수면 return
        return 0
    }
    
    let arr = s.map{$0}
    if s.count % 2 != 0{
        return 0
    }
    var stack: [String.Element] = []

    let cnt = arr.count
    
    for i in 0..<cnt{
        if stack.count > 0 && stack.last == arr[i]{
            stack.removeLast()
        }else{
            stack.append(arr[i])
        }
        
        if stack.count > cnt - i { // Stack 안에 있는 원소들의 갯수보다 남은 원소의 수가 적으면
            return 0
        }
    }

    if stack.count == 0{
        return 1
    }else {
        return 0
    }
}

다른 사람의 풀이

func solution(_ s:String) -> Int{
     var STK = [Character]()
     var arr = Array(s)

     for i in arr.indices {
         if STK.isEmpty { STK.append(arr[i]) }
         else {
             if STK.last! == arr[i] { STK.removeLast() }
             else { STK.append(arr[i]) }
         }
     }

     return STK.isEmpty ? 1 : 0
}

아니 분명 나도 저렇게 풀었는데 .. 왜 실패했지 ?

var arr = Array(s)
var arr = s.map{$0}

실험해본 결과 여기서 차이가 났다. s.map{$0}은 O(n)인건 알겠는데 그럼 Array(s)는 s.map{$0} 보다 빠르니 O(1) 인건가 ••• 앞으로 Array를 쓰자 ❗️