루프 불변식

면접 대비

시간 제한1초메모리 제한1024 MB

요약

괄호 문자열을 원형으로 이어 붙였을 때, 원래 문자열과 다르면서 균형 잡힌 회전 문자열을 하나 찾습니다. 없으면 no를 출력합니다.

난이도: 보통10점 중 5점
유형: 문자열, 누적 합, 문자열 매칭
정답자: 아직 제출이 없습니다

문제

역사학자 루나는 오래된 수도원의 기록 보관소를 살펴보다가 신비한 양피지 두루마리를 발견했다. 두루마리에는 '('와 ')' 두 종류의 기호만 적혀 있었다. 루나는 곧 이 기호열이 흥미로운 성질을 가진다는 것을 알아챘다. 빈 기호열에서 시작해 어떤 위치에든 '()'를 반복해서 끼워 넣으면 이 기호열을 만들 수 있다는 것이다. 역사학자들은 이런 기호열을 균형 잡힌 기호열이라고 부른다. 그림 L.1은 균형 잡힌 기호열의 예이다.

그림 L.1: 빈 기호열에 '()'를 차례로 끼워 넣어 만든 입력 2의 예.

수도원의 수석 사서는 최근 루나에게 이 지방의 일부 엘리트 수도사들이 원형 양피지에 글을 쓰는 습관이 있었다고 전했다. 그들의 생각으로는 두루마리에 적힌 글의 시작점을 바로 알아내지 못하는 사람은 그 내용을 알 자격도 없었다. 루나는 곧바로 양피지 띠의 가장자리를 살폈다. 역시나 띠의 왼쪽 끝과 오른쪽 끝이 정확히 맞물렸고, 이 양피지가 실제로 원형이었음을 보여 주었다. 왼쪽 끝과 오른쪽 끝을 맞대고 이제 원형이 된 양피지를 바라보며, 그녀는 찢어진 곳에서 시작하는 균형 잡힌 기호열이 양피지를 찢었을 때 나올 수 있는 유일한 기호열인지 궁금해한다. 시작점도 모른 채 글을 해독하려 해도 소용이 없으니 말이다.

입력

입력은 다음과 같다.

루나의 양피지 띠에 적힌 균형 잡힌 기호열 $s$ ( $2\leq |s|\leq 10^6$ )가 한 줄로 주어진다.

출력

원형 기호열을 잘라서 서로 다른 균형 잡힌 기호열을 얻을 방법이 없으면 "no"를 출력한다. 그렇지 않으면 그러한 기호열 중 아무거나 하나를 출력한다.

예제2

예제 1
입력
```
(()())(()())
```
예상 출력
```
no
```
예제 2
입력
```
()(())()
```
예상 출력
```
(())()()
```