LeetCode 20(Valid Parentheses, java)

0. 문제

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

 

1. 문제 설명

- 문제에서 문자열(s)이 주어진다.

- 문자열(s)은 괄호(), 중괄호{}, 대괄호[]로 이루어진다.

- 문자열 내부의 괄호가 순서대로 짝에 맞게 열리고 닫히는지를 파악하는 것이 문제의 핵심이다. 

 

2. 문제 해설

a) 첫 번째 접근

- 괄호의 순서와 짝을 파악하는 것이 이 문제의 핵심이다.

- 그러므로 괄호가 열리는 순서에 따라서 닫히는 순서를 파악해야 한다.

 

- 가장 마지막에 열린 괄호는 가장 먼저 닫힌다. (Last Open, First Close)

- 이와 유사한 순서를 갖는 자료구조는 Stack이다. (Last In, First Out)

- 그러므로 이 문제는 Stack을 이용하여 풀면 쉽게 해결할 수 있다. 

 

b) 두 번째 접근

- 우선 짝을 파악해야 하므로 가장 첫 번 재로 해야 할 일은 문자열의 길이를 파악하는 것이다.

- 모든 괄호가 짝을 이룬다고 가정했을 때, 문자열의 길이가 홀수라면 짝이 맞지 않는 것이기 때문이다.

 

c) 세 번째 접근

- 문자열 내부의 각 문자를 탐색해야 하므로, 두 번째 접근에서 파악한 문자열의 길이를 사용한다.

- 문자열의 길이만큼 for문을 돌려서 charAt() 메서드를 통해 각 문자를 접근 및 탐색한다. 

 

- 각 문자를 탐색하는 과정에서 열린 괄호가 등장하면 이는 Stack 자료구조에 저장(push)한다.

- 각 문자를 탐색하는 과정에서 닫힌 괄호가 등장하면 Stack의 가장 마지막에 삽입된 데이터를 추출(pop)한다.

 

- 가장 마지막에 열린 괄호와 가장 마지막에 닫힌 괄호의 짝이 맞지 않는다면, false를 반환한다.

- 그 외의 경우에는 true를 반환한다. 

 

d) 네 번째 접근

- 만약 문자열을 구성하는 괄호가 모두 닫힌 괄호인 경우를 생각해야 한다.

- 반대로 문자열을 구성하는 괄호가 모두 열린 괄호인 경우도 생각해야 한다.

- 이러한 경우에는 Stack 자료구조에 저장된 데이터의 수를 이용하여 판단할 수 있다. 

 

- for문으로 문자열을 탐색하는 과정에서 닫힌 괄호가 발견되는 경우, Stack에서 데이터를 추출한다.

- 그러나 이때 Stack에 아무 데이터도 존재하지 않는 경우, EmtpyStackException이 발생할 것이다. 

- 더불어, 이 케이스는 올바르지 않은 케이스이므로 false를 반환해야 한다. 

- 닫힌 괄호로 구성된 문자열이기 때문이다. 

 

- 반대로 문자열이 열린 괄호로만 구성되어 있는 경우, Stack에 계속해서 데이터가 저장될 것이다.

- 문제의 조건대로 괄호의 짝과 순서가 올바르게 구성된 문자열이라면 Stack에 아무것도 남아있으면 안 된다.

- 즉, 이 케이스는 올바르지 않은 케이스이므로 false를 반환해야 한다.

- 열린 괄호로 구성된 문자열이기 때문이다. 

 

- 다음 코드를 보면서 이해해보자. 

 

3. 정답 코드

class Solution {
    public boolean isValid(String s) {
        
        int len = s.length();
        
        if(len % 2 != 0) {return false;}
        
        Stack<Character> stack = new Stack<>();
        
        for(int i = 0; i < len; i++) {
            char curn = s.charAt(i);
            
            if(curn == '(' || curn == '{' || curn == '[') {
                stack.push(curn);
            }
            
            else if(stack.size() == 0) {return false;}
            
            else if(curn == ')') {
                if(stack.pop() != '(') {return false;}
            }
            else if(curn == '}') {
                if(stack.pop() != '{') {return false;}
            }
            else if(curn == ']') {
                if(stack.pop() != '[') {return false;}
            }
        }
        return stack.size() == 0;
    }
}