괄호 문자열

(와 )로만 이루어져 있는 문자열을 "괄호 문자열"이라고 한다.

다음 규칙으로 만들 수 있는 괄호 문자열을 "올바른 괄호 문자열"이라고 하자.

• 빈 문자열은 올바른 괄호 문자열이다.
• ""가 올바른 괄호 문자열이면, "()"도 올바른 괄호 문자열이다.
• ""와 ""가 올바른 괄호 문자열이면, ""도 올바른 괄호 문자열이다.

예를 들어, (), ()(), (()), (()(()))은 모두 올바른 괄호 문자열이다. 그러나, (, ))((, ()())((())은 모두 올바른 괄호 문자열이 아니다.

괄호 문자열 과 여러 개의 구간 가 주어진다.

당신의 목표는, 모든 구간 에 대하여 연속 부분 문자열 가 올바른 괄호 문자열이 되도록 만드는 것이다.

이를 위하여 당신은 에서 두 문자를 선택하여 서로의 위치를 교환하는 작업을 할 수 있다. 단, 작업의 수행 횟수를 최소화하여야 한다.

이러한 제약 조건을 지키며 목표를 달성해보자. 목표를 달성했다면 반드시 제출을 해야 득점할 수 있다.

총 다섯 개의 부분 문제를 해결해야 한다. 부분 문제는 상단의 "문제 " 버튼을 눌러서 선택할 수 있다.

문제 버튼을 누르면 괄호 문자열 와 구간 가 나타난다. 하나의 회색 가로 막대는 하나의 구간을 나타낸다. 그 구간에 대응하는 부분 문자열이 올바른 괄호 문자열이 되면 오른쪽의 X가 O로 바뀐다.

하단의 "현재 문제 초기화" 버튼을 누르면 해당 문제에 대해서만, 수행한 모든 작업을 취소하고 초기 상태로 돌아간다.

채점 방식

다섯 문제를 모두 해결하지 않아도 부분 점수를 받을 수 있다. 각 문제를 최소 횟수의 작업으로 해결하면, 각각 전체 점수의 20%를 받는다.