Nesting

🔗 문제 링크

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

❔ 문제 설명

A string S consisting of N characters is called properly nested if:

S is empty;
S has the form "(U)" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, string "(()(())())" is properly nested but string "())" isn't.

Write a function:

def solution(S)

that, given a string S consisting of N characters, returns 1 if string S is properly nested and 0 otherwise.

For example, given S = "(()(())())", the function should return 1 and given S = "())", the function should return 0, as explained above.

⚠️ 제한사항

• N is an integer within the range [0..1,000,000];

• string S consists only of the characters "(" and/or ")".

---

💡 풀이 (언어 : Python)

앞의 괄호 종류 3개 문제와 거의 흡사한 문제이다. 이 문제에서는 소괄호만 사용하기 때문에 조금 더 간결하게 풀어보았다. 앞에 예제에서도 숫자 변수 3개 사용하는 방법을 사용해도 될 것 같다. 시간복잡도는 $O(N)$

def solution(S):
    count = 0

    for s in S:
        if count < 0:
            return 0

        if s == "(":
            count += 1
        else:
            count -= 1

    if count == 0:
        return 1
    else:
        return 0