[Python] 프로그래머스 - 대중소 괄호 짝 맞추기

문제 설명

여섯 가지 괄호 '(', ')', '{', '}', '[', ']'로 이루어진 문자열이 바르게 닫힌 문자열인지 체크. 바르게 닫힌 문자열이란 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로, '[' 문자로 열렸으면 ']' 문자로, '{' 문자로 열렸으면 '}' 문자로 닫히는 문자열을 의미함.

- 제대로 닫히지 않은 문자열 예시: ((]], ([)]
- 제대로 닫힌 문자열 예시: [[(())]]{}

문자열 s가 주어졌을 때, 문자열 s가 바르게 닫힌 문자열일 경우 True를 그렇지 않으면 False를 리턴하는 코드를 작성할 것.

단, 문자열 s의 길이는 1 이상 40이하이며 문자열 s는 위의 6개 괄호 문자로만 이루어짐.

---

문제 접근

전형적인 스택 풀이 문제이다. 문자열 s를 처음부터 훑으면서 열린 괄호라면 push하고 닫힌 괄호라면 stack의 top과 비교한다. 비교 시 짝이 맞지 않다면 stack에 push한다.

이때, stack의 top이 닫힌 괄호라면 앞의 괄호가 닫히기 전에 짝이 맞지 않는 닫힌 괄호가 등장하는 것이므로 끝까지 탐색할 필요 없이 해당 문자열 s는 바르게 닫힌 괄호가 아니다. 따라서 바로 False를 리턴하도록 한다. 문자열 s의 끝까지 탐색이 끝나면 stack이 비어있는지 체크한다.

---

풀이

이를 코드로 표현하면 다음과 같다.

def solution(s):
    answer = True
    pair = {
        "{": "}",
        "(": ")",
        "[": "]"
    }
    stack = []
    
    for char in s:
        ## if stack is empty
        if not stack:
            if char in pair.keys():
                stack.append(char)
                continue
            else: # 앞선 괄호쌍이 소진되고 닫힌 괄호로 시작할 경우
                return False

        ## stack is not empty
        if pair[stack[-1]] == char:
            stack.pop()
        
        elif char in pair.keys():
            stack.append(char)

    return stack == []

짝이 맞는지 맞지 않는지는 딕셔너리를 정의해서 짝이 맞는지를 체크해주었다. 코드가 살짝 지저분하단 생각이 들었다. pair 딕셔너리에는 열린 괄호만 키로 갖고 있기 때문에 닫힌 괄호를 stack에 push해주게 되면 KeyError가 발생한다. 따라서 stack에 push할 때는 무조건 열린 괄호인지 아닌지 체크하는 부분이 필요하다. 아니면 아래처럼 push는 하되 stack의 top이 닫힌 괄호일 경우에는 무조건 False를 리턴하는 식으로 코드를 작성해도 된다 (문제 설명에 따르면 닫힌 괄호는 stack에 들어갈 수 없다). 

def solution(s):
    answer = True
    pair = {
        "{": "}",
        "(": ")",
        "[": "]"
    }
    stack = []
    
    for char in s:
        if not stack:
            stack.append(char)
            continue
        
        if stack[-1] not in pair.keys(): # 닫힌 괄호로 시작하게 되면 무조건 False
            return False
        
        if pair[stack[-1]] == char:
            stack.pop()
        
        else:
            stack.append(char)

    
    return stack == []

 

 

 

하지만, 아예 KeyError를 핸들링하면서 코드를 간결하게 하는 부분을 생각해보았다. 아예 닫힌 괄호도 딕셔너리 키로 추가해버리되 그에 상응하는 Value를 None으로 주는 방법이 있을 것이고, 아예 pair를 체크하는 부분을 딕셔너리가 아닌 다른 방법을 생각하는 것이다.

# 닫힌 괄호 체크 X
def solution(s):
    answer = True
    pair = {
        "{": "}","(": ")","[": "]",
        "]": None, ")": None, "}": None
    }
    stack = []
    
    for char in s:
        if stack and pair[stack[-1]]==char:
            stack.pop()
        else: # empty stack or not a pair
            stack.append(char)
    
    return stack == []

이렇게 되면 닫힌 괄호도 stack에 들어가지만 문제 로직은 달라지는 게 없다. 반면에 코드는 훨씬 간결해졌다! 예외를 덕지덕지 고려해주지 않아도 손쉽게 문제 해결이 가능하다. 하지만, 이 문제에서는 문자열 길이의 상한이 매우 짧지만 문자열이 매우 길어지고 닫힌 괄호로 시작하게 되면 문자열을 불필요하게 탐색하게 된다는 단점이 있을 듯하다.

번외로, 위처럼 딕셔너리로 pair 체크하지 않고 각 괄호 문자의 아스키 코드를 비교하는 방식으로도 pair 체크가 가능하다. 각 괄호 문자는 중괄호, 대괄호의 경우 열린 괄호와 닫힌 괄호가 아스키 코드 2씩 차이가 난다. 소괄호의 경우는 1씩 차이가 난다.

def solution(s):
    answer = True
    stack = []
    
    for char in s:
        if stack and 0 < ord(char)-ord(stack[-1]) <= 2:
            stack.pop()
        else:
            stack.append(char)
    
    return stack == []