%2020. 3. 12. 22:14에 작성된 글입니다%
https://www.acmicpc.net/problem/9012
9012번: 괄호
괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고
www.acmicpc.net
여는 소괄호 닫는 소괄호 덕지덕지 붙인 문자열 주고 여는 것과 닫는 것이 제대로 맞아떨어졌는지 확인하는 문제.
문제의 알고리즘 분류는 스택으로 되어 있던데, 스택까지 안 써도 조금만 생각해 보면 간단하게 풀 수 있다.
여는 소괄호를 1, 닫는 소괄호를 -1로 치고 쭉 더한다.
만약 이 문자열이 Vaild PS라면, 여는 소괄호의 갯수와 닫는 소괄호의 갯수는 같을 테니까 다 더하면 0이 나온다.
그러면 그냥 다 더하고 비교하는 식으로 짜면 되느냐 하면 그건 아니다.
())( 같은, 다 더해서 0 나왔는데 Valid PS가 아닌 경우가 존재하기 때문이다.
또 눈여겨 보아야 할 것은, 문자열을 처음부터 특정 위치까지 잘랐을 때 잘린 문자열에서의 여는 소괄호의 갯수가 항상 닫는 소괄호의 갯수보다 많거나 같다는 점이다.
그야 열지도 않았는데 닫을 수는 없는 노릇이니까 당연히 그렇다.
이것들을 잘 생각해 보고 코딩하면 된다.