[자바 알고리즘 인터뷰] 9장 스택,큐 (1) - 유효한 괄호

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

 

- 대중소 세 종류 괄호로 된 입력값이 유효한지 판별하라 

 

 

풀이 1) 스택 일치 여부 판별 

 

- 열림 괄호인 [,{,( 는 스택에 푸시(push)하고, 닫힘 괄호인 ),},]를 만날 때 스택에서 팝(pop)한 결과가 매핑 테이블 결과와 매칭되는지 확인 

 

- 매핑 테이블을 만들어 놓고 테이블에 존재하지 않으면, 즉 닫힘 괄호가 아닌 경우 무조건 푸시하고, 팝했을 때 열림 괄호가 아닌 경우 false를 리턴하도록 구현 

 

- 입력값이 유효하지 않을 경우, 예를 들어 닫힘 괄호가 두번 연달아 들어오는 경우 스택이 비어 있는데 닫힘 괄호인 경우가 생긴다. 이렇게 되면 중간에 스택이 비게 된다. 

 -> 이 경우에도 유효하지 않은 입력값이므로 false를 리턴하도록 처리 

 

- 팝 결과가 일치하지 않는지 확인하는 것 외에도 스택이 비어 있는지 여부를 함께 확인해 false 여부를 결정하게 함

 //중간에 스택이 비거나 팝 결과가 열림 괄호가 아닌 경우 유효하지 않음
 else if(stack.isEmpty() || table.get(s.charAt(i))!=stack.pop())
 {
     return false;
 }

 

 

 

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        //유효성 검증을 위한 스택 선언
        Deque<Character> stack = new ArrayDeque<>();

        //유효성 검증을 위한 매핑 테이블
        Map<Character,Character> table = new HashMap<>() {{
            put(')','(');
            put('}','{');
            put(']','[');
        }};
        
        //문자열을 문자 단위로 반복
        for(int i=0; i<s.length(); i++)
        {
            //닫힘 괄호가 아닌 경우 스택에 푸시
            if(!table.containsKey(s.charAt(i))){
                stack.push(s.charAt(i));
            }
            //중간에 스택이 비거나 팝 결과가 열림 괄호가 아닌 경우 유효하지 않음
            else if(stack.isEmpty() || table.get(s.charAt(i))!=stack.pop())
            {
                return false;
            }
        }

        //유효한 입력이 되려면 반복 완료 후 스택이 비어야 한다. 
        return stack.size() == 0;
    }
}

2밀리초