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

 

시간초과 문제

스택이 아닌 String 으로 문제를 접근하였을 때 시간 초과가 발생하였습니다.

while 문 내부에 for 문으로 데이터를 계속 수정하는 방식은 입력값이 클 경우에는 매우 효율적이지 못했습니다.

import Foundation

func solution(_ s:String) -> Int{
    var answer = s
    var sets = Set<Character>(answer.map { Character(String($0)) })
    while true {
        let previous = answer

        for set in sets {
            answer = answer.replacingOccurrences(of: "\(set)\(set)", with: "")
        }
        
        if previous == answer {
            break
        }
    }

    return answer.isEmpty ? 1 : 0
}

 

스택으로 시간초과 해결

스택으로 문제를 해결하면 시간복잡도가 O(n) 으로 줄게 됩니다.

import Foundation

func solution(_ s: String) -> Int {
    var stack: [Character] = []
    
    for char in s {
        if let last = stack.last, last == char {
            stack.removeLast()
        } else {
            stack.append(char)
        }
    }
    
    return stack.isEmpty ? 1 : 0
}