Brackets

🔗 문제 링크

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

❔ 문제 설명

A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:

S is empty;
S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.

Write a function:

def solution(S)

that, given a string S consisting of N characters, returns 1 if 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..200,000]

• string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".

---

💡 풀이 (언어 : Python)

옛날에 비슷한 주제의 문제를 풀어본 기억이 있는 듯 했지만, 푸는게 까다로웠다.
관건은 열어준 괄호의 순서와 반대로 닫아줘야 하기 때문에 열어준 괄호의 종류를 순서대로 기억하고 있어야 하고, 그리고 괄호 종류별 짝의 개수가 맞아야 한다.
풀이의 아이디어는 여는 괄호와 닫는 괄호를 딕셔너리로 연결해주고, 문자열을 읽으면서 여는 괄호의 반대 괄호를 찾아 리스트에 순서대로 넣어준다. 하지만 꺼내는 순서는 반대로 pop을 해서 조회하고 닫는 괄호 문자열이 나왔을 때 꺼낸 닫는괄호 문자열과 일치하는지 체킹한다. 시간복잡도는 $O(N)$

def solution(S):
    dic = {"[" : "]", "{" : "}", "(" : ")"}
    lis = []
    
    for s in S:
        if s in "]})":
            # 처음부터 닫는 괄호 나오는 경우의 수 막아주기
            if len(lis) == 0:
                return 0
            if lis.pop() != s:
                return 0
        else:
            lis.append(dic[s])
	# 열기만 하고 닫지 않은 괄호 존재 시 0 반
    if len(lis) != 0:
        return 0

    return 1