문제1011--압축풀기

1011: 압축풀기

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 809  통과: 126
[제출] [채점기록] [묻고답하기]

문제 설명

문자열을 압축하는 가장 간단한 방법은 반복되는 부분문자열(substring)을 하나로 묶는것이다. 예를 들어 문자열 ABCABCABCABC와 같이 반복될 경우 이를 (3ABC)로 묶을 수 있다.

다시 말해서 부분문자열 XX...X 와 같이 $D$번 나타날 경우 (DX)로 압축을 할 수 있다. 연속된 부분 문자열은 최대 $9$회 반복이 가능하다고 가정하자.

이런 방법을 이용해서 문자열CABABABABABABCC(6AB)C, C(2(3AB))C로 압축할 수 있다. 압축된 문자열이 주어졌을 때, 원 문자열로 복원하는 프로그램을 구현하라.

입력 설명

입력은 여러 개의 테스트 케이스로 구성된다. 입력의 첫 행에는 테스트 케이스의 수 $T$ 가 주어진다. $(1 \leq T \leq 300)$

테스트 케이스는 한줄에 하나의 문자열로 이뤄지며, 문자열은 대문자 알파벳, 그리고 숫자 $1$이상 $9$이하의 숫자와 문자, (, )로 이뤄져있다. 문자열의 최대 길이는 $50$자 이하다.

(DX)의 형태의 입력이 있을 경우 $D$는 반드시 $1$이상 $9$이하의 숫자이며, 문자열 X의 길이는 무조건 $1$이상이다.

출력 설명

각 테스트 케이스의 순서대로 복원된 문자열을 한 줄에 하나씩 출력한다. 복원된 문자열의 길이는 $1,000$자 이하다.

입력 예시 Copy

5
C(6AB)C
C(2(3AB))C
CO(1N)TEST
(2(2AB))
AAAAAAAAAAAAAAAAAAAAA

출력 예시 Copy

CABABABABABABC
CABABABABABABC
CONTEST
ABABABAB
AAAAAAAAAAAAAAAAAAAAA

출처/분류