Editorial

---

C

문제 요약:

?가 포함된 괄호로만 이루어진 문자열이 주어지는데,

?의 위치에 적절한 괄호를 넣어서 RBS가 되게 만들 수 있는 경우의 수가 두개 이상 존재하는지 여부를 묻는 문제이다.

문제 해설:

무조건 가능한 문자열

$($의 개수는 n/2개를 넘을 수 없으므로, 앞에서부터 등장하는 ?의 자리에 greedy하게 n/2개가 넘지 않게끔 $($를 채우고, 그 다음 등장하는 ?의 자리에는 $)$를 채우면 RBS가 완성된다.

문제에서 무조건 되는 문자열에 ?로 채운 문자열을 제공한다고 했으므로, 이것은 무조건 가능하다. 왜냐하면 $)$의 개수가 앞의 $($만 넘지 않으면 되기 때문이다.

앞의 문자열에서 어떤 $($와 $)$의 위치를 바꿀 수 있고, 바꾼 문자열이 RBS이면 답은 NO이고, 그렇지 않으면 YES가 된다.

이때, 만약 바꿔도 RBS가 되는 문자열이라면 마지막 $($과 처음 $)$를 바꾸었을 때에도 반드시 RBS가 된다.

왜냐하면 모든 위치에 대해 앞의 $)$의 개수가 $($의 개수를 넘지 않으면 RBS인데, 조건에 대해 가장 적게 영향을 미치는 변경이 마지막 $($와 처음 $)$를 바꾸는 것이기 때문이다.

따라서 마지막 $($와 처음 $)$를 swap해 보고, RBS가 되는지 여부를 체크하면 된다.