[LeetCode-자바] N_394 Decoding String

📜 문제

압축된 문자열을 풀어내는 문제이다.
decoding 규칙은 대괄호로 묶인 문자열을 앞선 숫자 만큼 반복한다.
중첩 괄호를 허용하며, 내부 괄호 먼저 decoding 한다.

생각하기

반례들을 통해 얻은 문제 포인트
1. 3[a2[c]] 처럼 중첩 괄호를 생각해야한다.
2. 숫자는 한 자리수라는 말이 없다.

stack을 사용함은 바로 떠올렸지만,,, 많은 반례들이 튀어나오고 1시간이 지나도 풀지 못해 풀이를 봤다.

스택을 한 개만 사용하고 숫자가 여러 자리수가 될 수 있음을 간과해 계속 살을 붙이다 보니 많이 길어지고 가독성이 떨어졌다.
아래는 내 틀린 코드다 ㅠ

 public static String decodeString(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuilder res = new StringBuilder();
        StringBuilder str = new StringBuilder();
        for(char cur : s.toCharArray()){
            if(cur == ']'){
                while(true){
                    char top = stack.pop();
                    if(Character.isDigit(top)){
                        StringBuilder num = new StringBuilder();
                        num.insert(0,top);
                        while(!stack.isEmpty()){
                            if(Character.isDigit(stack.peek())){
                                top = stack.pop();
                                num.insert(0,top);
                            }
                            else{
                                break;
                            }
                        }
                        int repeat =  Integer.parseInt(num.toString());
                        if(stack.isEmpty()){
                            for(int i=0;i<repeat;i++){
                                res.append(str);
                            }
                            str.setLength(0);
                        }
                        else{
                            for(int i=0;i<repeat-1;i++){
                                str.append(str);
                            }
                        }
                        break;
                    }
                    else if(Character.isAlphabetic(top )){
                        str.insert(0,top );
                    }
                    else continue;
                }
            }
            else {
                if(stack.isEmpty()&&Character.isAlphabetic(cur)){
                    res.append(cur);
                }
                else {
                    stack.push(cur);
                }
            }
        }
        while(!stack.isEmpty()){
            str.insert(0,stack.pop());
        }
        res.append(str);
        System.out.println(res);
        return res.toString();
    }

거두절미 하고 풀이 코드를 보며 설명하겠다.

✍ 부분 코드 설명

1. 변수 선언

 public static String decodeString(String s) {
        Stack<Integer> nStack =new Stack<>();
        Stack<StringBuilder> stack = new Stack<>();
        StringBuilder str = new StringBuilder();
        int n =0;
			...
    }

• nStack: 앞에 나온 숫자들을 저장하는 stack
• stack: 문자열들을 저장하는 stack
• str: 현재 문자열
• n: 현재 숫자

2. s 문자열 순회

  ...
 
 for(char cur: s.toCharArray()){
            if(Character.isDigit(cur)){
                n = n*10 + (cur-'0');
            }
            else if(cur == '['){
                nStack.push(n);
                n=0;
                stack.push(str);
                str = new StringBuilder();
            }
            else if(cur==']'){
                int k = nStack.pop();
                StringBuilder tmp = str;
                str = stack.pop();
                while(k-- >0){
                    str.append(tmp);
                }
            }
            else {
                str.append(cur);
            }
        }
}

1 .숫자, n 변수 업데이트

ex) 32[ab],
1) n = 0 * 10 + 3, n=3
2) n = 3 * 10 + 2, n=32

2. 여는 괄호

• 현재 숫자(n)를 숫자 스택 (nStack)에 삽입한다. (n 초기화)
• 현재 문자열(str)을 문자열 스택(stack)에 삽입한다. (str 초기화)

3. 닫는 괄호

• 숫자 스택에서 pop한 원소를 k에 저장
• tmp 변수에 현재 문자열 저장
• 현재 문자열에 tmp 문자열 k번 반복 삽입

4. 그 외, 현재 문자열에 저장

   

   이해를 돕는 그림 설명 ㅎ

🍳 전체 소스 코드

class Solution {
    public String decodeString(String s) {
                Stack<Integer> nStack =new Stack<>();
        Stack<StringBuilder> stack = new Stack<>();
        StringBuilder str = new StringBuilder();
        int n =0;
        for(char cur: s.toCharArray()){
            if(Character.isDigit(cur)){
                n = n*10 + (cur-'0');
            }
            else if(cur == '['){
                nStack.push(n);
                n=0;
                stack.push(str);
                str = new StringBuilder();
            }
            else if(cur==']'){
                int k = nStack.pop();
                StringBuilder tmp = str;
                str = stack.pop();
                while(k-- >0){
                    str.append(tmp);
                }
            }
            else {
                str.append(cur);
            }
        }
        System.out.println(str);
        return str.toString();
    }
}

✨ 결과

여기서 알아가는 건.. 문자로 표현된 여러 자릿수의 숫자를 숫자로 변환하여 저장해 나가는 방법이 젤 크다.

아직 갈길이 멀다 ㅠ