[Stack] Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

 

예전에 라인코테에서 똑같은 문제가 나왔었다.

당연히 스택문제이고, 정상적으로 bracket이 닫히려면 bracket의 종류와 순서를 보면 된다.

괄호는 열린괄호와 닫힌괄호로 나누어 관리한다.

짝이 있으므로 key-value관계에 착안하여 map으로 관리한다.

 

false를 리턴하는 경우는 예시와 같이 대칭으로 괄호가 닫히지 않는 경우이다.

이를 위해 Loop의 이전element와 다음 element를 비교하여, 짝지가 되는 경우는 pop을 아닌 경우는 push를 해줄것이다.

 

2번을 예시로 들면, ' ( ' 가 들어오면 stack에 쌓이고 다음 루프에서 ' ) '가 들어오면 if 조건을 충족하므로 stack이 비워지게 된다.

false를 리턴하는 4번의 경우 ' ( '가 stack에 쌓이고 다음 원소고 ' [ ' 가 들어오지만, if 조건을 충족하지 못하므로 이 역시 stack에 쌓인다. ' [ '를 제거하기 위해서는 ' ] ' 가 들어와야 하지만, ' ) '가 들어오므로 stack은 비워지지 않는다.

 

true or false 리턴