[Algorithm] Nesting

[hwangJi-dev]

💬 문제

https://app.codility.com/programmers/lessons/7-stacks_and_queues/nesting/

💬 Idea

• S를 돌면서 “(”가 나왔을 때는 스택에 집어넣는다. (즉, 스택에는 “(”만 저장된다.)
• “)”가 나왔을 때
  • 스택이 비어있다면, 중첩되지 않은 문자열을 뜻하므로 0을 리턴하고 함수를 종료한다.
  • 스택이 비어있지 않다면 “)”의 짝인 “(”가 스택에 1개 이상 들어있다는 의미이므로 스택의 마지막 원소를 pop하여 짝을 제거해준다.
• 해당 작업 수행 후 스택이 비어있지 않다면(== 스택에 “(”가 남아있다면) 중첩되지 않은 문자열임을 뜻하므로 0을 리턴하고, 스택이 비어있다면 1을 리턴하며 함수를 종료한다.

💬 풀이

public func solution(_ S : inout String) -> Int {
    var stack: [Character] = []
    
    for i in S {
        if i == "(" {
            stack.append(i)
        } else {
            if stack.isEmpty {
                return 0
            } else {
                stack.popLast()
            }
        }
    }
    
    return stack.isEmpty ? 1 : 0
}

소요시간 : 10분

시간 복잡도 : O(N)

평가표 : https://app.codility.com/demo/results/trainingUU25J9-BGK/