[leetcode] 20. 유효한 괄호 (Valid Parentheses)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

괄호로 된 입력값이 올바른지 판별하라. 

 

 

입출력 예시

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

 

생각과정

괄호가 올바르게 열리고 닫혔는지 판별하는 문제이다. 

pop으로 하나씩 꺼내서 비교하면 될 것 같다. 그런데 일일히 값을 비교해주면 너무 비효율적이다. 방법이 없을까?

 

강사님의 설명을 살짝 들어보니 dict의 ket value쌍이 있는 특징을 이용하면 된다고 한다. 이름이 dictionary의 dict형을 사전처럼 사용해보자!

 

풀이

내가 구현했지만 틀린 코드

dict = {
    ')': '(',
    '}': '{',
    ']': '['
}

flag = False
def valid(s: str) -> bool:
    for char in s:
        if char in dict:
            flag = True
        else:
            flag = False

    return flag

애용하는 flag를 사용해서 풀어보려고 했으나 정답이 아닌데도 True를 반환한다. 코드를 읽어보니 문제는 조건문에서 '('와 ')'의 쌍이 아니라 무조건 ')'가 있는 지만을 판별하기 때문이었다.

 

애초에 오늘 배운 개념인 stack을 사용하지도 않았다. 내 실력이 매우 창피해서 지워버리려고 했지만 이렇게 삽질한 것도 공부의 일환이니까 기록해두기로 했다.

 

아무튼, 풀이에서 구현한 코드를 보자.

 

첫번째 방식

def valid(s: str) -> bool:
    table = {
        ')': '(',
        '}': '{',
        ']': '['
    }

    stack = []

    for char in s:
        if char not in table:
            # dict에 char가 없으면 stack에 append한다 -> '({['를 넣어줌.
            stack.append(char)
        elif not stack or table[char] != stack.pop(): # 주의! 연산자의 우선순위에 신경쓸 것 (두 연결리스트의 병합에서도 나옴)
            return False

    return len(stack) == 0

이 간단한것도 구현하지 못하다니

 

stack과 dict 자료형을 이용한 코드이다.

for문으로 문자열 s를 쪼개준 다음 그 char가 table에 없으면 stack에 쌓아주는데, 이 조건문에서 여는 괄호가 들어가게 된다. 

 

반대로 table에 char가 있다는 말은 char가 닫는 괄호라는 말과 같고, elif문으로 판별을 하게 된다.

 

elif not stack or table[char] != stack.pop(): # 주의! 연산자의 우선순위에 신경쓸 것 (두 연결리스트의 병합에서도 나옴)
        return False

elif문을 살펴보면, 당연히 stack에 append를 해줬으니 stack은 비어있지 않을테고, table에 들어있는 값과 stack에서 뽑아준 값을 최종적으로 비교를 해준다. 

 

table[char] != stack.pop()를 보면 table[char]는 dict에서 char를 key값으로 value를 가져오고 stack.pop()으로 매칭되는 여는 괄호가 있는 지 판별한다. 다르면 당연히 False를 return하고 같다면 최종적으로 비교가 완료되어서 stack이 전부 pop이 되었는 지 확인하고 결과를 return하면 해결!

 

+

알아둬야하는 개념이 있어서 추가로 정리해본다.

연산자의 우선순위인데, 이 부분을 헷갈리면 전혀 다른 결과값이 나오므로 꼭 숙지해두자!

 

순위	연산자	설명과 예
1	[v1, ...], {v1, ...}, {k1: v1, ...}, (...)	리스트/셋딕셔너리/제너레이터 생성 혹은 컴프리헨션, 괄호에 쌓인 표현식
2	seq[n], seq[n:m], func(args...), obj.arr	인덱스, 슬라이스, 함수 호출, 속성 참조
3	**	지수
4	+x, -x, ~x	양수, 음수, 비트 연산 not
5	*, /, //, %	곱하기, 나누기(부동소수점), 나누기(정수), 나머지
6	+, -	더하기, 빼기
7	<<, >>	왼쪽 ㅣ프트, 오른쪽 시프트(비트 연산)
8	&	and(비트연산)
9	|	or(비트연산)
10	in, not in, is, is not, <, <=, >, >=, !=, =	멤버십과 균등 테스트
11	not x	부울 not(논리 연산)
12	and	부울 and
13	or	부울 or
14	if ... else	조건식
15	lambda	람다

 

 

두번째 방식

def valid(s):
    pair = {
        '}': '{',
        ')': '(',
        ']': '[',
    }
    opener = "({["
    stack = []

    for char in s:
        if char in opener:
            stack.append(char)
        else:
            if not stack:
                return False
            top = stack.pop()
            if pair[char] != top:
                return False

    return not stack

두번째 코드도 똑같이 dict 자료형과 stack을 사용한다. 다른 점은 처음에 opener 변수에 여는 괄호를 담아주고 시작하는 것이다.

전체적인 흐름은 첫번째 방식과 다르지 않으니 간단하게 차이점만 짚고 넘어가겠다!

---

마치며

정말 난 왜 이 정도로 간단한 코드도 구현하지 못할까...라는 회의감이 너무 강하게 든다. 이렇게 공부하면 언젠가 직접 구현할 수 있는 날이 올까..? 고민이 많은 하루다.

 

앞으로는 공부할 때, 흐름을 파악하면서 어떤 방식으로 코드를 짜는 지도 제대로 파악하고 암기해야겠다.