[JAVA] 백준 3012번 올바른 괄호 문자열

https://www.acmicpc.net/problem/3012

3012번: 올바른 괄호 문자열

위 문제는 백준 10422번 괄호 문제와 매우 비슷한 문제이나 푸는데 꽤나 애를 먹었다..

애를 먹은 부분은 시간초과 난 부분과 답이 맞은거 같은데 틀렸습니다 나오는 부분이었는데..

풀면서 어려웠던 부분을 기록해보려고 한다.

먼저 시간초과 난 부분,

메모리를 저장해주는 2차원 배열 d[][] 에 -1값으로 초기값을 세팅해주고(46~48번째 줄)

이후 저장된 값이 있으면, 재귀함수를 이어가는 것이 아니라 저장된 값을 바로 리턴해주지 않아서였다.(16~17번째 줄)

위와 같이 고치기 전에 나는 10422번 문제 처럼 단순히 d[startindex][endindex]>0 이면 return 해주었는데..

 

10422번 괄호 문제에서는, 길이에 대해 가능한 괄호 값만 구하면 됐기 때문에 0값이 저장되는 경우가 없어서 가능했던 것이고, 위 3012번의 경우는 특정 괄호가 지정된 위치에 이미 있는 상태에서 가능한 값을 구하는 것이기 때문에 0값이 저장되는 경우가 가능해서, -1로 미리 셋팅을 해주고 -1이 아닌 경우 저장된 값을 리턴해야 하는 것이었다.

그래서 시간초과가 나는 것이었다..

 

두번째 틀렸습니다 난 부분,

문제 조건에 '개수가 다섯 자리를 넘어가는 경우에는 마지막 다섯 자리만 출력한다.' 는 부분이 있었다.

주의해야 할 점은

- 다섯자리를 넘어가는 경우 마지막 다섯자리 시작부분이 0 인 경우에도 모두 포함하여 출력한다.

- 개수의 총 합에서 마지막 다섯자리를 구하는 것이기 때문에, 중간에 100000를 넘어가는 경우 100000를 더해주고 10000를 나눈 나머지 값을 더하면서 값을 누적한다.

위 내용을 생각하지 못해서 틀렸습니다가 된 것이었다..

 

위 두가지 명심하자.