[codeground] 57. 괄호

codeground - Practice - SCPC 3회 예선 - 57. 괄호
문제 : https://www.codeground.org/practice/practiceProblemList

---

조건
1. 빈 문자열은 올바른 괄호 문자열이다.
2. S1이 올바른 괄호 문자열이라면, (S1), {S1}, [S1] 모두 올바른 괄호 문자열이다.
3. S1과 S2가 올바른 괄호 문자열이라면, S1S2도 올바른 괄호 문자열이다. 

조건 1번에 의해 정답 ans의 초기값은 0이다.
조건 2를 위해서 스택을 만들고 여는 괄호인 경우 스택에 해당 괄호의 인덱스를 넣는다. 닫는 괄호인 경우 스택의 스택의 top에서 가장 최근의 여는 괄호 인덱스를 가져와서 여는 괄호와 현재 닫는 괄호의 짝이 맞다면 그 길이를 정답과 비교하여 최대값을 정답으로 갱신한다. ex. ((())) : 빨간색 괄호들이 짝이 맞는 경우고 이 경우 길이는 6이 된다.
조건 3을 위해서 올바른 괄호 문자열이 시작되는 인덱스(start_ind)를 따로 저장해둔다. 스택을 이용해서 괄호들의 길이를 비교하여 정답을 갱신하다가 스택이 비게 되는 경우 연속되는 올바른 괄호 문자열 길이를 구해야한다. 그 길이는 start_ind ~ 현재 닫는 괄호 인덱스 이다. ex. ()() 빨간색 괄호의 인덱스가 start_ind에 저장되고 조건 2 방법으로 파란색 괄호를 탐색할 때의 길이는 2인데 앞에 연속된 괄호 문자열이 있고 이를 고려한 괄호 문자열 길이는 4이다. 

시간복잡도는 O(N)이다. 여기서 N은 입력받는 괄호 문자열 길이다.

---

소스 코드 : https://github.com/fpdjsns/Algorithm/blob/master/codeground/57.%20%EA%B4%84%ED%98%B8.cppgithub.com/fpdjsns/Algorithm/blob/master/codeground/57.%20%EA%B4%84%ED%98%B8.cpp

fpdjsns/Algorithm

---

열린 괄호가 나오면 스택에 계속 넣고 닫히 괄호가 나오면 스택의 top에 위치하는 괄호와 비교해서 짝이 맞다면 sum+2 를 해주면서 sum값의 최대값을 ans에 저장한다. 만약 스택이 비어있거나 짝이 맞지 않다면 sum은 0으로 리셋하고 스택도 비워준다. 이를 문자열의 끝까지 탐색하면서 반복하였을 때의 ans값이 정답이 된다. 

...라는 알고리즘을 짰는데 틀렸다. 그래서 제출이력에서 맞은 사람들의 코드를 보고 sum값을 갱신할 때가 아니라 스택이 비어있는 경우만 ans값을 갱신하게 바꾸니까 만점을 받았다. 그런데 이렇게 코드를 작성하면 "(((())" 이 경우는 정답이 4인데 코드로는 0이 출력된다. 스택이 빈 경우가 없기 때문이다. 테스트케이스가 엄밀하지 않다는건 둘 째 치고, 오답이 뜨는 이유는 내 알고리즘이 잘못되었다는 것인데 무슨 테스트케이스에서 틀렸을지 감이 안잡힌다... 흑.... 일단 코드그라운드 QnA에 질문을 올렸다. 

이렇게 코드를 짜면 ((()(()(() 의 경우 올바른 결과가 안나온다. (정답이 2인데 내 코드대로 하면 6이던가 나옴)
QnA에서 감사한 분이 답글 달아주셔서 깨달았다.ㅠㅠㅠ 만족스럽게 푸는데 한 달 걸린듯
예외 TC를 생각해내는 것도 무척 중요한 것 같다.

조건 3을 처리하는 과정에서 잘못 알고리즘을 짜서 틀렸었다. 그래서 스택에 여는 괄호의 종류( (,{,[ )를 저장하지 않고 여는 괄호의 문자열 인덱스를 저장하고, 새롭게 start_ind를 만들어서 해결하였다.