스택을 활용한 문제

문제 

* input 10[ab]
* output abababababababababab
* <p>
* input a3[b2[c]v]
* output abccvbccvbccv

 

압축한 문자열을 원본 문자로 바꿔주는 알고리즘이다. 

들어올 수 있는 단어는 숫자[0 - 9] / 대괄호[] / 소문자 [a-z] 이며 [] 안의 문자를 앞의 숫자 만큼 출력하는 식이다. 

 

주의할 점은 대괄호 안에 대괄호가 있을 경우 안쪽의 문자를 중복으로 풀어야하므로 까다로울 수 있다.

 

처음엔 숫자랑 문자를 따로 스택에 저장하면서 처리하려고 했는데 오히려 그러면 인덱스 맞추는 부분에서 어려울 수 있어서 구현이 어려웠다.

 

스택에 들어갈 문자열을 continueStrBuilder 로 하고  isPrevNumber 값을 통해 continueStrBuilder이 어떤 형태의 문자인지 알려주는 역할을 한다. 그리고 다른 문자열이 들어왔을 때 elementStack 에 값을 넣는다. elementStack 일 경우 ']' 일 경우 elementStack 값을 파악하여 숫자일 경우 continueStrBuilder 를 갯수만큼 중복해서 elementStack에 넣고 문자일 경우 두 문자를 합치고 elementStack에 넣습니다.

 

이런 식으로 문자열을 처리하면서 만든 후 마지막에 stack에 있는 값들을 합쳐서 출력합니다. 

 

public class Solution {

    /**
     * input    10[ab]
     * output   abababababababababab
     * <p>
     * input    a3[b2[c]v]
     * output   abccvbccvbccv
     */
    private static boolean isNumber(char c) {
        return c - '0' >= 0 && c - '0' <= 9;
    }

    private static boolean isNumber(String s) {
        if (s == null) {
            return false;
        }
        try {
            Integer d = Integer.parseInt(s);
        } catch (NumberFormatException nfe) {
            return false;
        }
        return true;
    }

    private static boolean isLowerCase(char c) {
        return c - 'a' >= 0 && c - 'a' <= 27;
    }


    private static String getString(String s) {
        StringBuilder continueStrBuilder = new StringBuilder();
        Stack<String> elementStack = new Stack();
        boolean isPrevNumber = false;
        if (isNumber(s.charAt(0))) {
            isPrevNumber = true;
        }
        for (int sIndex = 0; sIndex < s.length(); sIndex++) {
            char c = s.charAt(sIndex);

            if (c == '[') {
                elementStack.push(continueStrBuilder.toString());
                continueStrBuilder = new StringBuilder();
                isPrevNumber = false;
            } else if (c == ']') {
                String lastestElement = elementStack.pop();
                while (!isNumber(lastestElement)) {
                    continueStrBuilder.insert(0, lastestElement);
                    lastestElement = elementStack.pop();
                }

                String substr = continueStrBuilder.toString();
                continueStrBuilder = new StringBuilder();
                int multipleNumber = Integer.parseInt(lastestElement);

                StringBuilder a = new StringBuilder();
                for (int iter = 0; iter < multipleNumber; iter++) {
                    a.append(substr);
                }
                elementStack.add(a.toString());

            } else if (Solution.isNumber(c)) {
                if (isPrevNumber == false && continueStrBuilder.length() > 0) {
                    elementStack.add(continueStrBuilder.toString());
                    continueStrBuilder = new StringBuilder();
                }
                continueStrBuilder.append(c);
                isPrevNumber = true;
            } else if (Solution.isLowerCase(c)) {
                if (isPrevNumber == true && continueStrBuilder.length() > 0) {
                    elementStack.add(continueStrBuilder.toString());
                    continueStrBuilder = new StringBuilder();
                }
                continueStrBuilder.append(c);
                isPrevNumber = false;
            } else {
                // error
            }

            System.out.printf("character %c, continueStr %s, stack str %s \n", c, continueStrBuilder.toString(), elementStack.toString());
        }
        StringBuilder result = new StringBuilder();
        for(String sub : elementStack) {
            result.append(sub);
        }
        return result.toString();
    }

    public static void main(String[] args) {
        String a = getString("10[ab]");
        System.out.println(a == "abababababababababab");

        String b = getString("a10[b2[c]v]");
        System.out.println(b.equals("abccvbccvbccvbccvbccvbccvbccvbccvbccvbccv"));
    }