[LeetCode] 20. Valid Parentheses

문제 링크 : https://leetcode.com/problems/valid-parentheses/

Valid Parentheses - LeetCode

 

소괄호 중괄호 대괄호가 짝이 맞는지 확인하는 문제로 stack을 이용하여 구현하였다. 

문제와 제약 조건은 아래와 같다. 

문자열이 1이라면 false로 반환하고 문자열을 하나씩 읽어가면서

(1) 여는 괄호면 stack에 push를 하고

(2) 닫는 괄호라면 짝을 찾은 후 stack pop을 하며

 

최종적으로 stack에 남아 있다면 false를 다 제거 되었다면 true를 반환하였다. 

 

 

구현한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public char findPair(char c) {
        char ans =' ';
        if(c=='}') {
            ans = '{';
        } else if(c==')') {
            ans =  '(';
        } else if(c==']') {
            ans = '[';
        }
        return ans; 
    }
    
    public boolean isValid(String s) {
        if(s.length()==1) {
            return false;
        }
        
        Stack<Character> stack = new Stack<>();
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(c=='(' || c == '{'|| c =='['){
                stack.push(c);
            } else {
                char pair = findPair(c);
               
                if(stack.contains(pair)) {
                    stack.pop();
                } 
            }
                
        }   
        
        if(stack.isEmpty()){
            return true;
        } else {
            return false;
        }
        
    }
}

 

여기서 문제가 생겼는데 만약 닫는 괄호 하나가 있다면 false로 반환해야 하는데 true로 반환되어서 생긴 문제 였다.

가령 아래와 같은 예제가 들어갔을 때에는 false로 나와야하는데 true로 나왔다.

생각을 해보니 마지막에 있는 원소를 pop해서 읽고, stack에서 push할지 pop을 할지 결정할 때에 stack이 이미 비었다면 false를 반환해야 했다. contains로 무조건 하면 안되고, 가장 위에 올라와 있는 괄호와 현재 읽는 괄호를 비교해서 계산을 해야했다. 

 

수정해서 짠 코드는 다음과 같다. 

import java.util.*;

class Solution {
    public char findPair(char c) {
        char ans =' ';
        if(c=='}') {
            ans = '{';
        } else if(c==')') {
            ans =  '(';
        } else if(c==']') {
            ans = '[';
        }
        return ans; 
    }
    
    public boolean isValid(String s) {
        if(s.length()==1) {
            return false;
        }
        
        Stack<Character> stack = new Stack<>();
        
        for(int i=0; i<s.length(); i++) {
            char c = s.charAt(i);
            if(c=='(' || c == '{'|| c =='['){
                stack.push(c);
            } else {
                char item = ' ';
                try {
                    item = stack.pop();
                } catch(Exception e) {
                    return false;
                }
                    
                char pair = findPair(c);
                
                if(item != pair) {
                    return false;
                }
            }
                
        }   
        
        return stack.isEmpty();
        
    }
}