oVeron

https://www.acmicpc.net/problem/24552 24552번: 올바른 괄호 첫번째 줄에 문자열 $S$가 공백 없이 주어진다. ($3 \leq \vert S \vert \leq 100\,000$, $\vert S \vert$는 홀수이다.) 답은 $1$ 이상이다. 즉, 지웠을 때 올바른 괄호열이 되는 문자가 적어도 하나 존재한다. www.acmicpc.net 관찰 N이 10만이기에 괄호를 하나씩 지워가며 풀었다간 O(N^2)의 시간복잡도로 시간초과가 난다. 다른 방법이 필요하다. 문자열 S에서 정확히 하나의 괄호만 지워야 하며, 답이 무조건 1 이상이므로, '(' 괄호의 수와 ')' 괄호의 수의 차는 무조건 1이다. 차가 0이라면 답은 0이며, 차가 2 이상이면 하나의 괄호만을 지워서는 ..

알고리즘/baekjoon 2023. 3. 20. 09:48