Description

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10^5.

---

주어진 인코딩된 문자열을 디코딩한 결과를 반환해야 합니다.

인코딩 규칙은 다음과 같습니다: k[인코딩된_문자열], 여기서 대괄호 안의 인코딩된 문자열이 정확히 k번 반복됩니다. 여기서 k는 양의 정수임이 보장됩니다.

입력 문자열은 항상 유효하다고 가정할 수 있습니다; 추가적인 공백은 없으며, 대괄호는 잘 형성되어 있습니다. 또한 원본 데이터에는 숫자가 포함되어 있지 않으며, 숫자는 반복 횟수 k만을 나타냅니다. 예를 들어, 3a나 2[4]와 같은 입력은 주어지지 않습니다.

테스트 케이스는 출력의 길이가 항상 10^5를 초과하지 않도록 생성됩니다.

예제 1:

입력: s = "3[a]2[bc]"
출력: "aaabcbc"

예제 2:

입력: s = "3[a2[c]]"
출력: "accaccacc"

예제 3:

입력: s = "2[abc]3[cd]ef"
출력: "abcabccdcdcdef"

제약 조건:

• 1 <= s.length <= 30
• s는 소문자 영어 알파벳, 숫자, 그리고 대괄호 '[]'로 구성됩니다.
• s는 유효한 입력임이 보장됩니다.
• s 내의 모든 정수는 [1, 300] 범위에 있습니다.

Solution

import java.util.Stack;

class Solution {
    public String decodeString(String s) {
        StringBuilder result = new StringBuilder();
        Stack<int[]> stack = new Stack<>();
        int repeatedLeft = -1;

        for (int i = 0; i < s.length(); i++) {
            char character = s.charAt(i);

            // reapted가 여러 자리 일 수 있으니 숫자의 왼쪽 위치를 기억
            if (Character.isDigit(character)) {
                if (repeatedLeft == -1) {
                    repeatedLeft = i;
                }
                // '[' 가 나오면 repeated를 구함
            } else if (character == '[') {
                int repeatedRight = i;
                int repeated = Integer.parseInt(s.substring(repeatedLeft, repeatedRight));
                // encoded_string 왼쪽 위치를 구하고, repeated와 왼쪽 위치를 push
                int encodedStringLeft = result.length();
                stack.push(new int[] { repeated, encodedStringLeft });
                repeatedLeft = -1;
            } else if (character == ']') {
                // encoded_string을 인코딩된 문자열을 repeated 만큼 반복
                int[] repeatedAndLeft = stack.pop();
                int left = repeatedAndLeft[1];
                int right = result.length();

                String encodedString = result.substring(left, right);
                int repeated = repeatedAndLeft[0];
                for (int j = 0; j < repeated - 1; j++) {
                    result.append(encodedString);
                }
                // 일반문자열이면 결과에 더함
            } else {
                result.append(character);
            }
        }

        return result.toString();
    }
}