[LeetCode] 20. valid Parentheses 문제풀이

[목차]

1. 문제 설명
2. 문제 생각
 2.1 풀이 설명
 2.2 성공케이스 설명(예제1)
 2.3 실패케이스 설명(예제3)

3. 문제 풀이
  3.1 Python
  3.2 Java 

1.  문제 설명

이 문제는 괄호({}, (), []) 를 입력받아서 괄호가 열고 닫는 것을 잘 매칭이 되는냐를 확인하는 문제이다. 

 

2. 풀이 생각

2.1 풀이 설명

이 문제는 자료 구조 Stack을 이용하는 아주 유명한 문제이다. Stack을 이용한다는 생각을 못했을 때에는 진짜 엄청 머리 아프게 풀었다.. 다양한 경우의 수가 있어서.. for문과 if문을 얼마나 썼던지.. 하지만 Stack을 이용하면 진짜 코드도 간단하고 생각도 간단하게 풀수 있다. 
아래 예를 들면 괄호 입력을 성공 케이스와 실패케이스로 설명해보겠다. 

1) 괄호 "(, [, {" 이 들어올 때 이 괄호 반대인 "), ], }"를 stack에 넣어준다. 
2) 괄호 "), ], }"이 들어올 때 stack에 있는 정보(pop)가 해당 괄호와 일치하지 않거나 stack이 비어있다면 False를 출력한다. 
3) 마지막에 stack이 비어있다면 괄호는 valid한것이 된다. 

한글 설명이 좀 어려운데 코드를 보면서 다시 설명하면 더 이해하기 쉽지 않을까 싶다

2.2 성공 케이스 설명 (예제1)

예제 1번을 가지고 설명을 해보겠다. 

먼저 "("이 들어오면 괄호 반대부호인 ")"를 stack.push를 해준다. stack을 그림으로 표시하자면 아래 그림과 같다. 

 2.3 실패케이스 설명(예제3) 

이번에도 똑같이 (가 맨처음 문자이기 때문에 아래와 같다. 

위를 보면 ] != ) 이 같지 않기 때문에 결국 유효하지 않은 괄호가 되서 False가 된다. 이 문제풀이법을 코드로 구현하면 아래와 같다. 

3. 문제풀이

3.1 Python

class Solution:
     def isValid(self, s: str) -> bool:
        stack = []
        for parentheses in s:
            if parentheses == "(":
                stack.append(")")
            elif parentheses == "{":
                stack.append("}")
            elif parentheses == "[":
                stack.append("]")
            elif not stack or stack.pop() != parentheses:
                return False                
        return not stack

 

3.2 Java

public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char inputBracket = s.charAt(i);
            if (inputBracket == '(') {
                stack.add(')');
            } else if (inputBracket == '{') {
                stack.add('}');
            } else if (inputBracket == '[') {
                stack.add(']');
            } else if (stack.isEmpty() || stack.pop() != inputBracket) {
                return false;
            }
        }
        return stack.isEmpty();
    }