[프로그래머스] 올바른 괄호 (lv.2)

#algorithms #python #programming

문제 주소

올바른 괄호

문제에 대한 첫인상

올바른 괄호를 체크하는 문제는 정말 많이 풀어본 문제였다.

특히 정보올림피아드에서 많이 나오는 문제이기 때문에 가볍게 풀 수 있었다.

첫번째 풀이

첫번째는 스택을 써서 풀어보았다.

스택은 파이썬 list를 쓰기 보다는 collections의 deque를 쓰는 것이 좋다.

스택을 써서 푸는 방법은 다음과 같다.

1. 문자열을 앞에서부터 차례대로 순회한다.
2. 만약 "(" 문자열이면 `push`한다.
3. 만약 ")" 문자열이면, 스택이 비어있는지 검사하고, 비어있으면 `False`를 리턴한다.
4. 그렇지 않으면 `pop`한다.
5. 모든 문자열 순회 뒤에 스택이 비어있다면 `True`를 리턴한다.

알고리즘이 간단하기에 이대로 풀기만하면 될 것 같다.

답

from collections import deque
def solution(s):
    st = deque()
    for i in s:
        if i == "(":
            st.append(i)
            continue
        if len(st) == 0:
            return False
        st.pop()
    if len(st) != 0:
        return False
    return True

하지만 간단하게?

하지만 간단하게 풀 수 있을 것 같았다.

그래서 아이디어가 있는데, JSON 파싱을 이용하는 것이다.

JSON을 파싱할 때, "[]" 배열 또한 문법에 들어간다.

따라서 모든 문자열을 "("를 "["로, ")"를 "]"로 바꾸고 파싱을 하고,

만약 파싱이 안되면 False, 되면 True를 리턴하도록 하면 어떨까? 🤔

그래서 다음과 같은 전략을 세웠다.

1. "(" -> "["
2. ")" -> "],"

그리고 파싱... 아주 간단한 전략이군! 😎 이라고 생각했다...

from json import loads
def solution(s:str):
    s = s.replace("(", "[") \
        .replace(")", "],")
    try:
        loads(s)
        return True
    except:
        return False

테스트1, 2에서 오류가 났다...

그 이유는 "()()" 이런 밖이 없는 경우가 문제였고,

"(())" 이렇게 중첩된 경우가 문제였다.

그래서 알고리즘을 추가했다.

1. "(" -> "["
2. ")" -> "],"
3. "[]"로 문자열을 감싼다.
4. ",]" -> "]"

이렇게 하면 ","가 쓸데없이 붙어있는 경우를 없앨 수 있지 않을까?

그렇게 아래 코드로 테스트를 돌렸다.

from json import loads
def solution(s:str):
    s = s.replace("(", "[") \
        .replace(")", "],")
    s = f"[{s}]"
    s = s.replace(",]","]")
    try:
        loads(s)
        return True
    except:
        return False

테스트는 모두 합격.

그리고 딱히 반례가 생각이 나지 않아서 바로 제출했다.

정말 충격적이군...

이제 반례찾기 시간~

자 무언가 이상한 반례가 있다는 것을 확인했다.

일단 첫번째로 문자열의 길이가 너무 길면 json 파싱 오류가 나는 것일까? 이렇게 생각했다.

그래서 "("*50000 + ")"*50000 이런 문자열을 테스트해봤다.

그랬더니 다음과 같은 오류가 발생했다.

RecursionError: maximum recursion depth exceeded while decoding a JSON array from a unicode string

아마 json 파싱을 할 때 재귀함수를 써서 하는 것 같았다.

그래서 만약 재귀 횟수를 늘려주면 어떨까? 하고 생각했다.

그리고 제출했다.

답

from json import loads
import sys
sys.setrecursionlimit(10**6)
def solution(s:str):
    s = s.replace("(", "[") \
        .replace(")", "],")
    s = f"[{s}]"
    s = s.replace(",]","]")
    try:
        loads(s)
        return True
    except:
        return False