괄호

면접 대비

시간 제한2초메모리 제한512 MB

요약

괄호 문자열이 주어질 때, 한 개 이하의 연속 구간을 뒤집어 전체를 올바른 괄호열로 만들 수 있는지 판정한다.

난이도: 보통10점 중 6점
유형: 그리디, 누적 합, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

(와 )로 이루어진 괄호 문자열이 올바른 괄호 문자열인지는 다음 규칙으로 정한다.

빈 문자열은 올바른 괄호 문자열이다.
$X$ 가 올바른 괄호 문자열이면 $(X)$ 도 올바른 괄호 문자열이다.
$X$ 와 $Y$ 가 올바른 괄호 문자열이면 둘을 이어 붙인 $Z = XY$ 도 올바른 괄호 문자열이다.

예를 들어 (()), ()(), (()())()는 올바른 괄호 문자열이고, (와 ())는 올바른 괄호 문자열이 아니다.

길이가 $n$ 인 괄호 문자열이 주어진다. 이 문자열은 올바르지 않을 수도 있다. 구간 뒤집기를 최대 한 번 해서 올바른 괄호 문자열로 만들 수 있는지 판별하라. 구간 뒤집기는 1부터 세는 두 인덱스 $l$ 과 $r$ ( $1 \le l \le r \le n$ )을 골라 닫힌 구간 $[l, r]$ 에 속한 괄호를 모두 뒤집는 연산이다. 뒤집으면 여는 괄호 (는 닫는 괄호 )가 되고, 닫는 괄호 )는 여는 괄호 (가 된다.

())(는 구간 $[3, 4]$ 를 뒤집으면 올바른 괄호 문자열이 된다. ()))는 구간 $[3, 3]$ 을 뒤집어도 되고 구간 $[2, 2]$ 를 뒤집어도 된다. 반면 )))(는 어떤 구간을 뒤집어도 올바른 괄호 문자열이 되지 않는다.

입력

첫 줄에 괄호 문자열이 주어진다. 길이는 1 이상 5000 이하이며, 문자열은 (와 )로만 이루어진다.

출력

구간 뒤집기를 최대 한 번 해서 올바른 괄호 문자열로 만들 수 있으면 possible을, 만들 수 없으면 impossible을 출력한다.

예제3

예제 1
입력
```
()))
```
예상 출력
```
possible
```
예제 2
입력
```
)))(
```
예상 출력
```
impossible
```
예제 3
입력
```
()
```
예상 출력
```
possible
```