Java) 프로그래머스 - 올바른 괄호

August 16, 2022

문제 링크

괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’ 문자로 닫혀야 한다는 뜻입니다. 예를 들어
”()()” 또는 “(())()” 는 올바른 괄호입니다.
”)()(“ 또는 “(()(“ 는 올바르지 않은 괄호입니다.
’(‘ 또는 ‘)’ 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

괄호의 짝이 맞는지 확인하려면 서로 짝이 맞는 괄호끼리 없애주면 된다. ()() 이런 괄호가 있을 때 짝이 맞는 두 괄호끼리 없애주면 하나도 남지 않는다. 그러면 이 괄호는 짝이 맞는 것이고 true를 리턴하면 된다.
- 하지만 ()( 이런 괄호들에서 짝이 맞는 괄호를 없애면 ( 하나가 남는다. 그러면 괄호의 짝이 맞지 않기 때문에 false를 리턴해야 한다.
위의 과정을 효과적으로 수행하기 위해 스택을 이용하면 편하다. 스택은 삽입한 순서대로 차곡차곡 쌓아서 넣은 순서와 반대로 꺼내기 때문이다. 그래서 ( 여는 괄호일 때엔 스택에 넣고 ) 닫는 괄호일 때엔 스택에서 괄호를 꺼내면 짝이 맞는 괄호를 없앨 수 있게 된다.
2번 과정을 수행하는 동안 닫는 괄호가 나와서 여는 괄호를 꺼내야 하는데 스택이 비어있다면 짝이 맞지 않는 것이니까 false를 리턴하고 탐색을 종료한다.
- 반대로 탐색을 끝까지 완료했는데 스택에 괄호가 남아있다면 역시 짝이 맞지 않는 것이다. false를 리턴한다.
- 탐색을 끝까지 완료했는데 스택이 비어있다면 모든 괄호의 짝이 맞는 것이다. true를 리턴한다.