[Leetcode 아주 상세한 문제풀이] 20. Valid Parenthesis - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 20번 문제 Valid Parenthesis 다.

우선 문제를 살펴보자.

 

리트코드 20번 문제 Valid Parenthesis 링크

Valid Parentheses - LeetCode

Valid Parentheses - LeetCode

 

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:
Input: s = "()"
Output: true

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

Example 3:
Input: s = "(]"
Output: false

 

 

문제 설명

문제를 간략히 살펴보면, 입력된 문자열 s는 다양한 종류의 괄호로 이루어져있다.

이때 괄호들의 짝이 맞는지, 그리고 열고-닫고 순서가 제대로 되어 있는지를 판단하는 문제다.

예를 들어 문제 예시 1번에서 처럼 괄호가 ()로 주어졌다면 열리고 닫히는 짝이 맞다.

따라서 이 경우 True를 리턴하면 된다.

문제 예시 2번 역시 3가지 다른 종류의 괄호가 있지만 결국 같은 짝끼리 열리고 닫히는 짝이 맞다.

그래서 이 경우도 True를 리턴하면 된다.

하지만 문제 예시 3번에서 처럼 열리는 괄호가 ( 이고 닫히는 괄호가 ]일 경우 그 짝이 맞지 않기 때문에 False를 리턴해야 한다.

문제에 대한 이해가 어렵지 않기 때문에 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제에 대한 접근 방법은 여러가지 일 수 있을 것 같은데 이번에는 dictionary를 이용해 풀어보도록 하겠다.

우선 문제 접근 방법은 입력된 문자열 s의 문자를 하나씩 받아들여

그것이 여는 괄호라면 stack에 쌓아준다.

그리고 문자를 하나씩 계속 받아들이다가 닫는 괄호를 만나게 되면 stack에 쌓여있던 여는 괄호를 pop 해준다

이렇게 하다보면, 만약 여는-닫는 괄호 쌓이 맞게 순서대로 되어 있다면 최종적으로 stack에는 아무것도 남아있지 않게 된다.

 

 

문제 풀이

코드를 한 번 살펴보자.

우선 문자열을 받아들이는 함수를 정의해 준다 (line 1)

그리고 여는-닫는 괄호 쌍에 대한 dictionary를 만들어 준다 (line 4)

입력된 문자열을 for loop를 통해 하나씩 불러온다 (line 6)

이때 불러온 문자가 여는 괄호라면 stack에 추가해준다 (line 7-8)

만약 불러온 문자가 닫는 괄호라면 (line 9)

우선 stack이 비었는지를 확인해 본다 (line 10)

만약 stack이 비어있다면 현재 불러온 닫는 괄호의 짝이 없기 때문에 false를 return 해주면 되기 때문이다 (line 11)

만약 불러온 닫는 괄호와 쌍을 이루는 (dictionary에 찾은) 여는 괄호가 stack에 쌓여있는 여는 괄호 중 가장 마지막에 쌓인 여는 괄호와 짝이 맞는다면 stack에서 여는 괄호를 제거(pop) 해준다 (line 12-13)

이도저도 아니라면 false를 return해준다.

그리고 for loop의 마지막에 stack의 길이가 0인지 아닌지를 return 해준다 (line 17)

만약 길이가 0이라면 여는-닫는 괄호가 모두 짝이 맞아 여는 괄호가 다 제거된 상태이기 때문에 true가 return되고

그 외의 경우는 false가 return되기 때문이다.

 

 

문제 풀이 코드

def isValid(s):
    stack = []
    opening_brackets = {'(', '[', '{'}
    bracket_pairs = {')': '(', ']': '[', '}': '{'}
 
    for char in s:
        if char in opening_brackets:
            stack.append(char)
        else:
            if not stack:
                return False
            if stack[-1] == bracket_pairs[char]:
                stack.pop()
            else:
                return False
 
    return len(stack) == 0
 
# Example usage
string = "({[}])"
print(isValid(string))

 

 

관련 문제

리트코드 3번 Longest substring without repeating characters 문제풀이

리트코드 5번 Longest palindromic substring 문제풀이

리트코드 49번 Group anagram 문제풀이

리트코드 76번 Minimum window substring 문제풀이

리트코드 125번 Valid palindrome 문제풀이

리트코드 242번 Valid anagram 문제풀이

리트코드 424번 Longest repeating character replacement문제풀이

리트코드 647번 Palindromic substrings문제풀이

 

20. Valid Parenthesis