Decode String (Stack)

LeetCode의 Queue, Stack 튜토리얼의 마지막 섹션의 세 번째 문제인 Decode String이다.

Explore - LeetCode

일정한 규칙으로 주어진 문자열을 해독하는 것이 목적인데 문제의 규칙은 다음과 같다.

• 문자열에 k[encoded_string] 포맷이 있다면 encoded_string을 k번 반복해서 이어 붙인 것과 같다.

• k는 자연수 값으로만 주어진다. encoded_string은 문자열 또는 k[encoded_string] 패턴을 포함하고 있다.

• 문자열은 공백을 포함하지 않고 소문자, 숫자, '[', ']' 문자로만 이루어져 있으며 괄호('[', ']')는 항상 짝이 맞다.

• 2[4], 3a 같은 포맷에 맞지 않는 문자열은 주어지지 않는다.

예를 들어 "3[a]" 같은 문자열이 주어진다면 이를 "aaa"처럼 해독해서 반환해야 한다는 것이다. 물론 이렇게 편하게 주어지지 않고 "3[ab3[c]d3[e]]" 처럼 중첩된 포맷이 주어질 수 있다. 이 경우 가장 안쪽부터 해석해야 하기 때문에 "3[ab3[c]d3[e]]" => "3[abcccdeee]" => "abcccdeeeabcccdeeeabcccdeee"처럼 해석돼야 할 것이다. 하지만 문자열이 항상 k[encoded_string] 포맷으로 제공되는 게 아니라 "abc"처럼 그냥 문자열만 주어지거나 "3[a]bc"처럼 포맷 뒤에 추가적으로 문자열이 주어질 수 있다. 그렇기 때문에 여러 경우의 수를 생각해보는 게 필요하다.

 

일단 문제 특성상 포맷 안에 포맷이 있기 때문에 스택 자료구조를 활용하거나 재귀적인 방법을 활용할 수 있을것 같은데 이번 튜토리얼이 Queue와 Stack을 연습하기 위한 것이기 때문에 스택 자료구조를 활용한 풀이를 시도해보았다.

 

기본적인 생각은 일단 문자열 자체에서 k[encoded_string] 형태를 유지하는 것이다. 예를 들어 "abc3[d]ef" 처럼 주어진다면 abc, ef는 따로 마지막에 결과 문자열에 붙이고 "3[d]" 부분만 파싱 하는 로직을 기반으로 시작하였다. 이는 String으로 주어진 문자열을 toCharArray 메서드를 이용하여 char 형 배열로 바꿔서 하나하나 읽는 방식으로 구현했다. 문자열에서 읽게 되는 문자는 다음처럼 4가지가 있다.

• a, b, c, d, ..., z: 일반 알파벳 문자.

• 0, 1, 2, ..., 9: 일반 숫자 문자.

• [ : k[encoded_string]에서 반복할 문자열을 여는 괄호.

• ] : k[encoded_string]에서 반복할 문자열을 닫는 괄호.

여기서 명심해야 할 것은 문자열에서 한 글자씩 읽을 때 지금 읽고 있는 알파벳 문자가 포함된 문자열이 반복(encoded_string)의 전체 문자열이 아니란 것이다. 패턴 내부에 패턴이 또 존재할 수도 있고 패턴 전후로 일반 문자열이 포함되어 있을 수도 있다. 예를 들어 "3[abc2[d]e]" 같은 문자열의 경우 "abc" 까지는 "3[~]"에 포함된 패턴의 문자열이지만 중간에 패턴 "2[d]"로 얻는 문자열과 패턴 뒤의 "e" 문자열도 "3[~]" 패턴에 포함시켜야 한다. 왜냐면 이는 다 같이 k, 위의 문자열에서는 3으로 반복되는 문자열이기 때문이다.

 

그래서 생각해본 것은 k[encoded_string]이 있다면 스택에 k, 그리고 encoded_string을 순서대로 삽입하는 것이다. 이때 encoded_string에서는 내부의 k[encoded_string] 패턴을 발견하기 전까지의 문자열만 스택에 삽입한다. 그리고 내부의 패턴을 처리한 후에 스택을 확인해서 스택에 이미 최근에 문자열이 삽입된 적이 있다면 이 패턴이 다른 패턴의 내부에 있는 중첩된 패턴이라고 판단, 하나의 문자열로 합치는 과정을 반복한다.

그림으로 보이면 위와 같다. k, encoded_string을 만날 때마다 파싱 해서 스택에 삽입하는데 "2[d]" 패턴에서 ']' 문자를 만난다면 패턴이 종료됐다는 것으로 인지하고 스택에 삽입된 데이터를 꺼내서 파싱 한다. 그렇게 생성된 "dd" 문자열은 스택이 비어있지 않는 이상 다른 패턴의 내부에 있는 패턴이라는 것을 의미하기 때문에 다시 스택에 삽입하기 전 스택의 제일 위에 있는 데이터를 확인한다. 만약 스택의 제일 위에 알파벳으로 구성된 문자열, 즉 encoded_string이 삽입되어 있다면 이 패턴 문자열들의 깊이(내부 패턴이 더 깊다고 할 때)를 맞추기 위해 그 문자열을 꺼내서 이번 패턴에서 만든 문자열의 앞에 붙여서 다시 스택에 삽입한다.

내부 패턴 뒤에 있는 문자 'e'에도 비슷하게 적용한다. 그리고 "3[abc2[e]e]"의 마지막 ']' 문자를 만났을 때도 스택에서 k, encoded_string을 빼서 문자열을 반복시킨다. 그리고 스택이 비어있다면 모든 패턴 문자열을 처리한 것이기 때문에 이를 결과 문자열에 추가한다. 이때 위에서 언급했듯이 패턴 뒤에도 문자열이 붙어있을 수 있기 때문에 마지막 문자까지 탐색했을 때 스택에 아직 문자열이 남아있을 수 있다.

이때는 그냥 간단하게 스택에 아직 남아있는 문자열을 결과 문자열에 이어 붙여서 반환해주면 된다. 왜냐면 이 문자열은 어떤 패턴에 포함된 것이 아니기 때문에 반복 처리를 할 필요가 없기 때문이다. 이런 로직을 바탕으로 구현한 코드는 다음과 같다.

import java.util.Stack;


class Solution {
    private StringBuilder result = new StringBuilder();
    private Stack<String> repeatedString = new Stack<>();
    
    public String decodeString(String s) {
        char[] characters = s.toCharArray();
        int index = 0;
        int limit = characters.length;
        
        StringBuilder firstString = new StringBuilder();
        while(index < limit && isCharacter(characters[index])) {
            firstString.append(characters[index++]);
        }
        if(firstString.length() > 0) result.append(firstString.toString());
        
        while(index < limit){
            if(isCharacter(characters[index])){
                StringBuilder repeatString = new StringBuilder();
                while(index < limit && isCharacter(characters[index])){
                    repeatString.append(characters[index++]);
                }
                if(!repeatedString.empty() && isCharacter(repeatedString.peek().charAt(0))){
                    repeatString.insert(0, repeatedString.pop());
                }
                repeatedString.push(repeatString.toString());
            } else if(isInteger(characters[index])){
                StringBuilder repetition = new StringBuilder();
                while(index < limit && isInteger(characters[index])){
                    repetition.append(characters[index++]);
                }
                repeatedString.push(repetition.toString());
            } else if(characters[index] == '[') {
                index++;
            } else if(characters[index] == ']') {
                StringBuilder repeatString = new StringBuilder();
                String string = repeatedString.pop();
                int repetition = Integer.parseInt(repeatedString.pop());
                index++;
                
                while(repetition-- > 0) {
                    repeatString.append(string);
                }
                
                if(repeatedString.empty()){
                    result.append(repeatString);
                } else {
                    while(!repeatedString.empty() && isCharacter(repeatedString.peek().charAt(0))){
                        repeatString.insert(0, repeatedString.pop());
                    }
                    repeatedString.push(repeatString.toString());
                }
                
            }
        }
        
        return result.toString() + (repeatedString.empty() ? "" : repeatedString.pop());
    }
    
    private boolean isCharacter(char ch){
        return ch >= 'a' && ch <= 'z';
    }
    
    private boolean isInteger(char ch){
        return ch >= '0' && ch <= '9';
    }
}

기본적으로 index 변수를 따로 유지하면서 반복문 외부, 내부에서 조건에 따라 증가시키면서 문자열을 참조하고 있다. 코드가 좀 길어졌기 때문에 중요한 부분으로 잘라서 설명하면 다음과 같다.

        StringBuilder firstString = new StringBuilder();
        while(index < limit && isCharacter(characters[index])) {
            firstString.append(characters[index++]);
        }
        if(firstString.length() > 0) result.append(firstString.toString());

먼저 이 부분은 문자열의 맨 앞에 있는 비패턴 문자열("abc3[d]"의 "abc")을 따로 분리하는 과정이다. 다른 패턴에 속하지 않았기 때문에 result라는 결과 문자열(정확히는 StringBuilder)에 제일 먼저 삽입하고 있다. 만약 그런 문자열이 없다면 스택에 삽입하지 않아야 한다. 공백 문자열("")이 삽입되기 때문에 나중에 스택에서 문자열을 꺼내볼 때 문제가 발생하기 때문이다.

            if(isCharacter(characters[index])){
                StringBuilder repeatString = new StringBuilder();
                while(index < limit && isCharacter(characters[index])){
                    repeatString.append(characters[index++]);
                }
                if(!repeatedString.empty() && isCharacter(repeatedString.peek().charAt(0))){
                    repeatString.insert(0, repeatedString.pop());
                }
                repeatedString.push(repeatString.toString());
            }

그리고 전체 문자열을 탐색하기 위한 while 반복문 내부의 첫 번째 조건인 isCharacter에서는 지금 탐색하고 있는 문자가 알파벳 문자인지 확인하고 있다. 이는 encoded_string에 포함된 알파벳 문자열을 파싱 하기 위한 것으로 인덱스를 증가시켜가며 알파벳 문자들을 StringBuilder에 포함시켜 문자열(repeatString)을 완성하고 있는데 위에서 언급했듯이 현재 탐색하고 있는 문자열이 "3[abc2[d]e"의 "abc"일지 "dd"일지 "e"일지 모르기 때문에 스택을 확인해야 한다. 만약 현재 문자열이 "abc"라면 스택에는 "3" 밖에 들어있지 않기 때문에 isCharacter 조건에 부합하지 않아 스택에 그대로 "abc" 문자열을 삽입한다.

 

만약 현재 문자열이 "e"라면 어떨까? 스택에는 "3", "abcdd"가 삽입되어 있을 것이다("2[d]"를 처리하는 과정은 일단 생략한다). 가장 최근에 삽입된 문자열이 알파벳 문자열(peek 메서드로 얻은 문자열의 첫 글자를 isCharacter 메서드에 넘겨서 확인한다)이기 때문에 이는 현재 패턴에 포함되어야 한다. 그래서 StringBuilder의 insert 메서드를 활용하여 가장 최근에 삽입된 문자열("abcdd")과 현재 문자열("e")을 이어 붙여서 다시 스택에 삽입하는 것이다. 이때 "abcdd"는 스택에서 삭제돼야 할 것이다.

 

어떤 패턴도 없이 그냥 "abc" 문자열만 주어지거나 현재 탐색하는 문자열이 "3[abc]ef"의 "ef"처럼 패턴 파싱이 종료된 후에 혼자 놓여 있는 문자열인 경우 스택은 비어있기 때문에 가장 최근에 스택에 삽입된 문자열을 참조하는 peek() 메서드를 호출하면 에러가 발생한다. 그렇기 때문에 스택(repeatedString)이 비어있지 않은지 확인하는 조건이 필요하다.

            } else if(isInteger(characters[index])){
                StringBuilder repetition = new StringBuilder();
                while(index < limit && isInteger(characters[index])){
                    repetition.append(characters[index++]);
                }
                repeatedString.push(repetition.toString());
            } 

만약 정수("3[abc]"의 "3")를 파싱 하는 경우 단순히 문자열 자체로 스택에 삽입해준다. 파이썬과는 달리 스택에 여러 자료형을 삽입할 수 없기 때문에 일단 문자열로 저장하고 나중에 정수로 파싱 해서 사용하기 위해서다. 정수인지 확인하는 isInteger 메서드를 활용하여 인덱스를 증가시키면서 파싱 하는 과정은 문자열을 파싱 하던 것과 비슷하다.

            } else if(characters[index] == '[') {
                index++;
            }

원래는 '[' 문자를 만났을 때 '[' 문자 다음부터 문자열을 파싱 해서 스택에 삽입하는 로직이 구현되어 있었다. 하지만 어차피 위에서 구현한 문자열 처리 로직에서 똑같이 처리할 수 있기 때문에 불필요한 코드 중복을 줄이고 인덱스를 다음 문자로 넘기는 기능만 남겨두었다.

            } else if(characters[index] == ']') {
                StringBuilder repeatString = new StringBuilder();
                String string = repeatedString.pop();
                int repetition = Integer.parseInt(repeatedString.pop());
                index++;
                
                while(repetition-- > 0) {
                    repeatString.append(string);
                }
                
                if(repeatedString.empty()){
                    result.append(repeatString);
                } else {
                    while(!repeatedString.empty() && isCharacter(repeatedString.peek().charAt(0))){
                        repeatString.insert(0, repeatedString.pop());
                    }
                    repeatedString.push(repeatString.toString());
                }
                
            }

패턴을 닫는 ']' 문자를 만난다면 스택에 최소한 두 개의 값이 저장되어 있어야 한다. 바로 k[encoded_string]의 k와 encoded_string이다. 만약 "3[abc]"라면 "3", "abc"가 저장되어 있을 것이기 때문에 각각 string 변수(encoded_string), repetition 변수(k)에 저장한 후 반복문을 통해 k만큼 encoded_string을 반복한다. 이때 문자열끼리 이어 붙이는 것은 StringBuilder를 활용한다.

 

그리고 스택이 비어있다면 제일 바깥쪽의 패턴까지 다 처리한 것이기 때문에 result 결과 문자열에 삽입한다. 그렇지 않다면 "3[abc2[d]]"에서 "2[d]"처럼 아직 바깥쪽에 패턴이 남아있다는 것이기 때문에 스택에서 가장 최근에 삽입된 문자열부터 꺼내서 알파벳 문자열인지 확인한다. 그리고 알파벳 문자열("abc")이라면 아까처럼 insert 메서드를 이용해 앞쪽에 이어 붙인 후 모든 문자열을 다 붙였으면 다시 스택에 삽입한다.

        return result.toString() + (repeatedString.empty() ? "" : repeatedString.pop());

그리고 마지막으로는 result 결과 문자열을 실제 String으로 생성하고 스택에 다른 문자열이 남아있는지(패턴에 포함되지 않은 문자열) 확인 후 있다면 결과 문자열 뒤에 붙여서 반환한다. 예를 들어 "3[abc]de"를 처리했다면 result에는 "abcabcabc"가 저장되어 있고 스택에는 "de"가 남아있을 것이다. 왜냐면 "de"도 알파벳 문자열이기 때문에 맨 처음 조건(isCharacter)에서 문자열로 파싱 되어 스택에 저장되기 때문이다. 그래서 스택에 남아있는 문자열을 결과 문자열에 붙여서 반환해주는 것이다.

 

하지만 코드가 70줄을 넘어가기 때문에 효율적 또는 직관적이라고 하긴 어렵지 않을까? 개선을 위해 다른 사람의 풀이(더 빠른 실행 속도)를 찾아보니 다음처럼 구축한 것을 볼 수 있었다.

class Solution {
    public String decodeString(String s) {
        Stack<Integer> num = new Stack<>();
        Stack<StringBuilder> str = new Stack<>();
        StringBuilder sb = new StringBuilder();
        int i = 0;
        for (char ch : s.toCharArray()) {
            if (ch >= '0' && ch <= '9') {
                i = i * 10 + (ch - '0');
            } else if (ch == '[') {
                num.push(i);
                str.push(sb);
                sb = new StringBuilder();
                i = 0;
            } else if (ch == ']') {
                StringBuilder decodeStr = str.pop();
                for (int times = num.pop(); times > 0; times --) {
                    decodeStr.append(sb);
                }
                sb = decodeStr;
            } else {
                sb.append(ch);
            }
        }
        return sb.toString();
    }
}

이 코드에서는 정수를 파싱 할 때 StringBuilder를 사용하지 않고 이전 숫자에 10을 곱해서 아스키 문자에서 '0'을 뺀 값을 더하는 방식으로 파싱 하고 있었다. 아스키 특성상 '1'에서 '0'을 빼면 1이 되는 특성을 활용한 것이다. 그리고 정수를 저장하기 위한 스택과 문자열을 저장하기 위한 스택을 따로 구축했는데 문자열의 경우 StringBuilder 객체 자체를 담는 스택으로 생성한 것을 볼 수 있었다. 항상 원시 타입(실제로 원시 타입은 아니지만)만 스택에 넣을 생각을 했었는데 이렇게 StringBuilder 객체를 담는 것도 괜찮은 것 같다.

 

어쨌든 위 코드에서는 문자를 하나하나 파싱 하면서 알파벳 문자일 경우 StringBuilder 객체에 담고 있다. 이 객체는 '[' 문자를 만났을 경우 스택에 저장되는데 이후 sb 변수에 새로운 StringBuilder 객체를 생성하여 새로운 문자열을 받아들일 준비를 하는 것이다. 그와 동시에 정수도 스택에 삽입하는데 삽입한 이후 새로운 정수를 받아들이기 위해 0으로 초기화해주고 있다.

 

패턴의 끝인 ']' 문자를 만났을 때는 StringBuilder 스택에 저장했던 객체를 꺼낸 다음 Integer 스택에 저장했던 정수를 꺼내서 그만큼 이어 붙인다. 이때 현재 StringBuilder 객체와 스택에서 꺼낸 객체는 각각 현재 패턴 문자열과 바깥 패턴 문자열을 의미한다. 예를 들어 "3[abc2[d]]"라면 StringBuilder 스택에서 꺼낸 decodeStr에는 "abc" 문자열이 저장되어 있을 것이며 현재 문자열을 담는 StringBuilder 변수 sb에는 "d" 문자열이 저장되어 있을 것이다. "abc2[d]"를 "abcdd"처럼 만들어야 하기 때문에 decodeStr의 뒤에 sb 변수를 이어 붙이는 과정을 스택에 저장된 times, 예시에서는 2만큼 반복하는 것이다. StringBuilder끼리 이어 붙일 수 있다는 점을 잘 활용한 것이다. 그리고 이렇게 이어 붙인 StringBuilder를 sb 변수에 다시 대입해서 새로 추가되는 문자들이 이 합쳐진 문자열에 추가되도록 하고 있다.

 

 

처음 풀 때는 새벽에 풀어서 그런지 테스트 케이스를 많이 놓쳤다. 그래서 여러 번 제출해보면서 놓친 테스트 케이스를 반영하여 수정하는 방식으로 풀었는데 실제 코딩 테스트에서는 제출 실패 시 감점이 있을 수 있으니 좋지 않은 습관이라 생각한다. 문제를 이해하고 여러 상황의 테스트 케이스를 작성해서 검증해보는 습관을 들여야 할 것이다.