[백준] 1662번 - 압축 (Java)

 

<풀이>

문자열을 순차탐색해서 ')'가 나올 때까지 계속 스택에 저장한다.

')'를 만나면 스택에 저장했던 문자들을 하나씩 꺼낸다.

'('를 만나면 꺼낸 문자들을 문자열로 만들어서 괄호 앞의 숫자만큼 루프를 돌려서 문자열에 머지한다.

이걸 반복해서 괄호안의 문자들을 모두 정리한 후 남은 문자열을 다시 붙여서 최종 길이를 출력한다.

 

<코드>

import java.util.Scanner;
import java.io.IOException;
import java.util.Stack;
import java.lang.StringBuilder;

//[백준] 1662번 - 압축 (Java)

public class Main {
    static char ch[];
    static int str_len = 0;

	public void InputData() throws IOException
	{
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        str_len = s.length();
        ch = s.toCharArray();
	}
	
	public void Solve() {
        Stack<Character> stack = new Stack<>();
        String str = new String();
        //int len = ch.length();
        // 1. 괄호 문자열 처리
        for (int i=0; i<str_len; i++) {
            if (ch[i] == ')') { // ')'를 만나면 머지작업 시작
                StringBuilder sb = new StringBuilder();
                while(!stack.isEmpty() && stack.peek() != '(') {
                    char c = stack.pop();
                    //sb.append(c); // 스택의 문자를 문자열에 붙이기
                    sb.insert(0,c);
                }
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop(); // '(' 제거

                    //System.out.println("loop ="+stack.peek());
                    int loop = stack.pop()-'0';
                    if (loop > 0) { // 괄호 앞의 숫자가 0이상일 때 수행
                        str += sb.toString();
                        //System.out.println(str);
                        String tmp = "";
                        for (int j=1; j<loop; j++) {
                            //str += str; // 괄호 안의 문자열을 숫자만큼 반복해서 늘리기
                            tmp += str;
                        }
                        str += tmp;
                    }
                    //System.out.println(loop+" : "+str);
                }
            } else {
                stack.push(ch[i]);
            }
        }

        //for (char c : stack) System.out.print(c+" ");
        //System.out.println();
        
        // 2. 스택에 남은 문자가 있으면 마저 머지하기
        while (!stack.isEmpty()) {
            //str.append(stack.pop());
            str += stack.pop();
        }
        System.out.println(str.length());

	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출>

 

<분석>

메모리 초과가 발생하는 것은 문자열을 합칠 때 + 연산을 사용해서 인것으로 의심된다.

이를 StringBuilder로 대체 했음에도 계속해서 메모리 초과가 발생한다.

문자열을 다시 재조립하는 과정에서 많은 메모리가 필요한 것으로 보인다.

출력값이 문자열의 길이만 출력하면 되기 때문에 문자열 머지 과정은 생략하고 길이만 다루도록 하자.

 

괄호안의 문자열 길이만 재서 다시 스택에 푸쉬한 다음 "*"을 추가로 푸쉬해서 기존 문자열과 구분한다.

사실 이 아이디어는 기존 다른 풀이에서 차용한 것이데 이 아이디어를 떠올리지 못하면 해결하기가 어려울 것 같다.

 

<코드 최종>

import java.util.Scanner;
import java.io.IOException;
import java.util.Stack;

//[백준] 1662번 - 압축 (Java)

public class Main {
    static char ch[];

	public void InputData() throws IOException
	{
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        ch = s.toCharArray();
	}
	
	public void Solve() {
        Stack<String> stack = new Stack<>();
        for (char c : ch) {
            if (c != ')') {
                stack.push(c+"");
            } else {
                int count = 0;
                // 괄호안의 문자열 길이 측정
                while (!stack.peek().equals("(")) {
                    // *이면 그 다음은 길이이므로 다시 pop해서 누적합하고, 아니면 +1한다.
                    if (stack.pop().equals("*")) { // 그 다음은 이전에 만든 문자열의 길이
                        count += Integer.parseInt(stack.pop());
                    } else {
                        count++;
                    }
                }
                stack.pop(); // "("이므로 삭제한다
                // 괄호 앞의 숫자이므로 괄호안의 길이만큼 곱해서 다시 푸쉬하고 *도 추가한다.
                String len = (count*Integer.parseInt(stack.pop()))+"";
                stack.push(len);
                stack.push("*");
            }
        }

        // 전체 길이 구하기
        long ans = 0;
        while (!stack.isEmpty()) {
            //ans += stack.pop().equals("*") ? Integer.parseInt(stack.pop()) : 1;
            if (stack.pop().equals("*")) { // 그 다음은 이전에 만든 문자열의 길이
                ans += Integer.parseInt(stack.pop());
            } else { // 괄호 밖 잔챙이들은 +1씩 해줌
                ans++;
            }
        }
        System.out.println(ans);
	}
    
	public static void main(String[] args) throws IOException
	{
		Main m = new Main();
		m.InputData();///입력
		//코드를 작성하세요
        m.Solve();
	}
}

 

<제출 결과>