코딩테스트 연습 - 짝지어 제거하기

문제 풀이 아이디어

N이 최대 1,000,000

일단 문제에 나온 예시대로 구현한다면 매번 문자열을 완전탐색해야 하므로 O(N)의 시간복잡도가 필요합니다. 문자열을 Array로 바꿔서 구현한다면 element를 삭제하는데 O(N)의 시간복잡도가 필요합니다. 추가적으로 할 수 있을 때까지 짝지어 제거해야 하므로 O(N)의 시간복잡도가 필요합니다. 종합하면 O(N^3)의 시간복잡도입니다.

따라서 문제에서 나온대로 구현하면 100% 시간초과입니다. N이 백만이라면 무조건 O(N) 이하의 알고리즘을 사용해야 합니다.

Stack을 활용하자!

stack의 대표적인 유형 중에 하나가 괄호를 짝 짓는 문제입니다. 이 문제도 괄호 대신 문자열을 짝지을 뿐 괄호 문제와 완전히 동일한 문제입니다. 따라서 stack을 활용해서 풀면 baab 같은 경우에 문자열을 2번 탐색하지 않고 1번의 탐색만으로도 짝을 지어 제거할 수 있습니다.

문자열 s를 완전탐색하면서 stack이 비었을 때는 push합니다. stack에 다른 element가 있을 때는 last와 비교해서 같으면 pop, 다르면 push 하면 됩니다.

모두 실행한 이후에 stack이 비었다면 1을 아니라면 0을 리턴하면 됩니다.

이렇게 하면 문자열 s를 한번만 탐색하면 되기 때문에 O(N)의 시간복잡도를 가지게 됩니다.

코드

func solution(_ s:String) -> Int {

    var stack = [Character]()
    
    for c in s {
        if stack.isEmpty {
            stack.append(c)
            continue
        }
        
        if stack.last! == c {
            _ = stack.popLast()!
        } else {
            stack.append(c)
        }
    }

    return stack.isEmpty ? 1 : 0
}