Valid Parentheses

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

Valid Parentheses - LeetCode

 

주어진 문자열의 괄호들이 제대로 닫혀있는지 물어보는 문제이다.
정상적으로 닫혀 있다면 순서대로 닫혀야 하므로 스택을 이용한 문제이다.
스택을 공부할 때 가장 기본적으로 나오는 문제이다. 사실 이와 같은 형태의 문제를 보았을 때 처음 보는 경우에는 왜 스택이 필요한지 이해가 되지 않을 수도 있다.

 

스택의 개념을 머리에 넣고 주어진 문자열을 차례대로 넣었다가 빼는 것을 확인해 보면 마지막에 넣은 것을 먼저 빼는 스택의 성질이 괄호를 정확히 순서대로 닫아준다는 것을 확인할 수 있다.
아래는 문제를 해결한 코드이다.

import java.util.*;

class Solution {  
    public boolean isValid(String s) {  
	  // Java의 경우 tack, LinkedList 후에 추가된 클라스인 ArrayDeque의 성능이 좋은 것으로 알려져 있다.
        Deque<Character> stack = new ArrayDeque<>();  
        
        for(int i = 0; i < s.length(); i++){  
            char c = s.charAt(i);  
            while(true){  
	         // 1. 스택이 비어있거나, 짝이 맞지 않는다면 문자열을 스택에 넣고 다음으로 넘어간다.
                // 2. 1조건이 맞지 않는다면 스택이 비어있지 않고, isPair(짝) 인 것이기에 
                //    짝에 맞는 스택의 값을 빼내준다. 이후 순차적으로 다시 비교하기 위해 c에 값을 할당 하면 
                //    while 문이 반복되면서 처리한다.
                
                if(stack.isEmpty() || !isPair(stack.peekLast(), c)){  
                    stack.offerLast(c);  
                    break;  
                }else {  
                    stack.pollLast();  
                    if(stack.isEmpty()){  
                        break;  
                    }else{  
                        c = stack.pollLast();  
                    }  
                }  
            }  
        }  
  
	  // 스택이 비어있다면 모든 괄호의 값들이 짝이 맞아 제거 된 것이므로 valid 하다
        return stack.isEmpty();  
    }  
  
    public boolean isPair(char a, char b){  
        return (a =='(' && b ==')')  
                || (a =='{' && b =='}')  
                || (a =='[' && b ==']');  
    }  
}

 

짝이 맞는 괄호일 때 while 문을 이용하여 연속적으로 확인하여 중첩된 괄호를 확인할 수 있다.
isPair의 경우 신규 값인 b의 값이, 스택에 있던 a의 값을 닫는 형태인지 체크하고 있다.