[프로그래머스] 올바른 괄호 (lv.2)
Tags: python, programming, algorithms
Published: 2023-11-16 05:46:16

## 문제 주소

[올바른 괄호](https://school.programmers.co.kr/learn/courses/30/lessons/12909)


---

## 문제에 대한 첫인상

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

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

---



## 첫번째 풀이

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

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

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


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


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


---
{% spoiler 답 %}
```python
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
```

![정답결과1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/57qvtgyvkv76gpaot0tk.png)
{% endspoiler %}

---


## 하지만 간단하게?

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

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

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

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

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

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



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


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


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


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

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

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

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


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


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

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


```python
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
```


테스트는 모두 합격.

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


![정답인줄1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n7qd0b6flzwfey63u5ux.png)


![정답인줄!!!](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/soy31zru1hu472vycteg.png)


![Youdontsay](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/y1daac7pgtz3byvr1kf0.png)

정말 충격적이군...

---


### 이제 반례찾기 시간~

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

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

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

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

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


![gotcha](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tkv2vv68crjzz1k4gjvx.gif)

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

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

그리고 제출했다.

---

{% spoiler 답 %}
```python
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
```
![정답결과2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8ypw7or3mt7vtjsxx9ll.png)
{% endspoiler %}

---

역시 정답이었어! 😎

여러분도 한 종류의 괄호에 대한 올바른 괄호를 체크하는 문제는 json을 쓰길 바란다~



![iamgatsby](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tomayrh6dogo7e6tcd3r.gif)