Problems
문자열을 압축하는 가장 간단한 방법은 반복되는 부분문자열(substring)을 하나로 묶는것이다. 예를 들어 문자열 "ABC"가 "ABCABCABC"와 같이 반복될 경우 이를 "(3ABC)"로 묶을 수 있다. 다시 말해서 부분문자열 X 가 X...X 와 같이 D번 나타날 경우 "(DX)"로 압축을 할 수 있다.
연속된 부분 문자열은 최대 9회 반복이 가능하다고 가정하자. 이런 방법을 이용해서 문자열 "CABABABABABABC"를 "C(6AB)C", "C(2(3AB)C"로 압축할 수 있다.
압축된 문자열이 주어졌을 때, 원 문자열로 복원하는 프로그램을 구현하라.
Input
첫 행에는 테스트 케이스의 수 T(1≤T≤300)가 주어진다. 테스트 케이스는 한 줄에 하나의 문자열로 이뤄지며, 문자열은 대문자 알파벳, 그리고 숫자 1 이상 9 이하의 숫자와 문자 '(', ')'로 이뤄져있다. 문자열의 최대 길이는 50자 이하다.
"(DX)"의 형태의 입력이 있을 경우 D는 반드시 1 이상 9 이하의 숫자이며, 문자열 X의 길이는 무조건 1 이상이다.
Output
각 테스트 케이스의 순서대로 복원된 문자열을 한 줄에 하나씩 출력한다. 복원된 문자열의 길이는 1,000자 이하다.
Example
5
C(6AB)C
C(2(3AB))C
CO(1N)TEST
(2(2AB))
AAAAAAAAAAAAAAAAAAAAA
CABABABABABABC
CABABABABABABC
CONTEST
ABABABAB
AAAAAAAAAAAAAAAAAAAAA
Source
Online Contest
You must sign in to write code.