드론 기동 매크로 전개

문제

드론 관제 시스템은 기동 명령 시퀀스를 매크로 문자열 로 압축해 저장합니다. 영소문자 하나가 기동 명령 하나이며, 반복되는 구간은 k(시퀀스) 표기로 압축합니다. k(시퀀스)는 괄호 안 시퀀스를 k번 반복한 것과 같고, 표기는 얼마든지 중첩될 수 있습니다.

예를 들어 3(ab2(c))는 ab 뒤에 c를 2번 반복한 abcc를 다시 3번 반복한 abccabccabcc를 뜻합니다.

매크로 문자열 s가 주어질 때, 전개된 기동 시퀀스를 반환하는 solution(s)를 작성하세요. 단, 저장 과정에서 손상된 매크로가 섞여 있을 수 있으므로 아래 규칙을 모두 만족할 때만 유효한 매크로로 봅니다.

• 여는 괄호 (와 닫는 괄호 )는 정확히 짝이 맞아야 합니다.
• 모든 ( 바로 앞에는 반복 횟수 k가 있어야 하고, 모든 숫자(연속된 숫자열)는 반드시 바로 뒤에 (가 와야 합니다.
• 반복 횟수 k는 앞자리가 0이 아닌 십진수이며 k ≥ 2여야 합니다. (0으로 시작하거나 1(ab)처럼 1회 반복인 표기는 손상된 것으로 간주)
• 괄호 안 시퀀스는 비어 있으면 안 됩니다. (2()는 손상된 표기)

반환 규칙:

1. s가 유효하지 않으면 문자열 "INVALID"를 반환합니다.
2. 유효하지만 전개 결과 길이가 100000을 초과하면 문자열 "TOO LONG"을 반환합니다.
3. 그 외에는 전개된 문자열을 반환합니다. (빈 매크로 ""는 유효하며 ""를 반환)

예시

제약 조건

• 0 ≤ s.length ≤ 200
• s는 영소문자, 숫자(0~9), (, )로만 구성됩니다.
• 반복 횟수 자체는 자릿수 제한이 없습니다. 전개 길이가 매우 커질 수 있으므로 "TOO LONG" 판정은 실제로 다 전개하지 않고도 내릴 수 있어야 합니다.

시간 복잡도 목표: O(n + L) — n은 s의 길이, L은 전개 길이(판정 상한 100001로 캡)