조명 스크립트 기호 정리

문제

공연장 조명 제어 스크립트는 소괄호 (, )로 동시 점등 그룹을, 대괄호 [, ]로 반복 블록을 표시합니다. 기호를 손으로 입력하다 보니 짝이 맞지 않거나 서로 다른 종류가 엇갈리게 겹친 스크립트가 종종 들어옵니다.

스크립트 s는 (, ), [, ] 네 문자로만 이루어져 있습니다. 올바른 구조는 다음과 같이 정의합니다.

• 빈 문자열은 올바르다.
• A와 B가 올바르면 A와 B를 이어 붙인 문자열도 올바르다.
• A가 올바르면 (A)와 [A]도 올바르다.

즉 짝이 맞아야 하고, 종류가 서로 엇갈려 겹칠 수 없습니다. (([)]는 올바르지 않습니다.)

스크립트를 올바른 구조로 만들기 위해 지워야 하는 문자의 최소 개수를 반환하는 solution(s) 함수를 작성하세요. 문자를 새로 넣거나 위치를 바꿀 수는 없고, 지우는 것만 가능합니다.

예시

예시 2 설명: 인덱스 1의 (와 인덱스 3의 ]를 지워 "[]"를 남기는 것이 최선입니다. 짝이 맞지 않는 닫는 기호만 지우는 방식으로는 ] 두 개를 지운 뒤에도 [, (가 남아 모두 4개를 지우게 됩니다.

예시 3 설명: 인덱스 5의 [를 지우면 "[()]()"가 되어 한 개만으로 올바른 구조가 됩니다.

제약 조건

• 0 ≤ s.length ≤ 100
• s는 (, ), [, ] 로만 구성됩니다.
• 답은 항상 존재합니다 (전부 지우면 빈 문자열이므로 올바릅니다).

시간 복잡도 목표: O(n³)