Write a function that reverses characters in (possibly nested) parentheses in the input string.

Input strings will always be well-formed with matching **()**s.

Example

• For inputString = "(bar)", the output should be**solution(inputString) = "rab"**;
• For inputString = "foo(bar)baz", the output should be**solution(inputString) = "foorabbaz"**;
• For inputString = "foo(bar)baz(blim)", the output should be**solution(inputString) = "foorabbazmilb"**;
• For inputString = "foo(bar(baz))blim", the output should be**solution(inputString) = "foobazrabblim"**.Because "foo(bar(baz))blim" becomes "foo(barzab)blim" and then "foobazrabblim".

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] string inputString

  A string consisting of lowercase English letters and the characters ( and ). It is guaranteed that all parentheses in inputString form a regular bracket sequence.

  Guaranteed constraints:

  0 ≤ inputString.length ≤ 50.

• [output] string

  Return inputString, with all the characters that were in parentheses reversed.

풀이

• nested 형식 주의 (괄호 안의 괄호)
  • 괄호 안의 괄호는 (abc(de)) → abced → decba
  • 따라서 괄호 안의 괄호는 별도의 리버스가 불필요하다.

String solution(String inputString) {
    // 1. 첫 번째 "(" 를 찾는다. 없으면 -1 반환
    int firstIdx = inputString.lastIndexOf("(");
    // 2. 첫 "(" 이 후의 ")" 를 찾는다.
    int lastIdx = inputString.indexOf(")", firstIdx);
    // 3. firstIdx ~ lastIdx 사이의 문자열을 뒤집는다.
    // 4. "(" 가 없을 때 까지 반복한다.
    
    // while 문 조건은 "(" 가 없을 때 까지 하는 것
    while (firstIdx != -1) {
        // 괄호안의 문자열을 뒤집는다.
        String str = new StringBuilder(inputString.substring(firstIdx + 1, lastIdx)).reverse().toString();
        // 괄호 왼쪽의 문자열 구분
        String first = inputString.substring(0, firstIdx);
        // 괄호 오른쪽의 문자열 구분
        String last = inputString.substring(lastIdx + 1);
        // 세 개의 문자열 머지
        inputString = first  + str + last;
        // 괄호 탐색
        firstIdx = inputString.lastIndexOf("(");
        lastIdx = inputString.indexOf(")", firstIdx);
    }
    
    return inputString;
}