20. Valid Parentheses

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

Valid Parentheses - LeetCode

난이도: Easy

 

Given a string 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. Note that an empty string is also considered valid.

 

stack을 사용하면 좋은 전형적인 문제이다.

여는 괄호가 나왔을 때, 추가로 여는 괄호는 나와도 관계 없으나 닫는 괄호는 직전에 열린 괄호와 맞게 나와야 한다.

앞에서부터 여는 괄호를 stack에 넣고 닫는 기호가 등장하면 pop하는 형식으로 구현했다.

 

여는 괄호, 닫는 괄호, 소괄호, 중괄호, 대괄호를 어떻게 구분해야 할까 고민을 많이 했다.

enum을 적절히 사용하면 코드 작성이 이쁘게 되지 않을까 했는데,

기본 개념이 잘 잡혀있지 않아 일단 생략했다.

저번에 다룬 indexOf 메소드를 활용하여 해당 그룹에 현재 살펴보고 있는 괄호가 있는지 체크하도록 구현했다.

String은 단순히 char형을 더하는 것으로는 부족하고, 실수 연산처럼 String이 중간에 껴있어야 가능하다.

 

import java.util.Stack;

class Solution {
    public boolean isValid(String s) {
        String openingParentheses = "({[";
        String closingParentheses = ")}]";
        String smallParentheses = "()";
        String mediumParentheses = "{}";
        String largeParentheses = "[]";
        
        Stack<Character> openers = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            char frontOfS = s.charAt(i);
            
            if (openingParentheses.indexOf(frontOfS) != -1) {    // opening
                openers.push(frontOfS);
            } else if (closingParentheses.indexOf(frontOfS) != -1) {     // closing
                if (openers.isEmpty()) return false;
                
                char lastOfClosers = openers.pop();
                String openerCloserPair = ""+ lastOfClosers + frontOfS ;
                
                if (smallParentheses.indexOf(openerCloserPair) == -1 &&
                    mediumParentheses.indexOf(openerCloserPair) == -1 &&
                    largeParentheses.indexOf(openerCloserPair) == -1) {
                    return false;
                }
            }
        }
        return openers.isEmpty();
    }
}

 

역시나 답안에서도 같은 방식으로 접근했다.

 

 

approach 1: stacks

 

답안은 적절한 자료구조로 이전에 살펴본 hash map을 사용했다.

닫는 괄호가 key, 여는 괄호가 value인 hash map을 만든다.

현재 살펴보는 문자를 mapping.containsKey 메소드를 사용하여 닫는 괄호인지 체크하고,

stack의 top인 여는 괄호에 mapping.get 메소드를 사용하여 매칭된 닫는 괄호와 같은지 확인한다.

이런식으로 작성하면 불필요한 연산을 대폭 줄일 수 있다.