[BOJ] 1662 압축

문제

www.acmicpc.net/problem/1662

1662번: 압축

풀이

1) 메모리 초과 및 중간에 괄호 있는 문자열 판별 X (Ex 32(123(12)352(5678)))

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	Stack<String> stack = new Stack<String>();
    	int idx = 0, g_cnt=0,len=0;
    	String[] pressed = br.readLine().split("");
    	String str = "";
    	len = pressed.length;
    	//계산
    	while(idx<len) {
    		while(!pressed[idx].equals("(")&&!pressed[idx].equals(")")) {
    			str+=pressed[idx];
    			idx++;
    		}
    		if(pressed[idx].equals("(")) {
    			stack.add(str);
    			stack.add("(");
    			str = "";
    			idx++;
    		}
    		else {
    			if(stack.peek().equals("("))
    				stack.add(str);
    			String repeat = stack.pop();
    			stack.pop();
    			String front = stack.pop();
    			String tmp = repeat;
    			int k = front.charAt(front.length()-1)-'0'-1;
    			front = front.substring(0,front.length()-1);
    			for(int i=0;i<k;i++)
    				tmp = tmp+repeat;
    			stack.add(front+tmp);
    			idx++;
    		}
    	}
    	str="";
    	while(!stack.isEmpty())
    		str = stack.pop()+str;
    	//System.out.println(str);
    	System.out.println(str.length());
	}
} 

2) 스택 활용 성공 코드

import java.io.*;
import java.util.*;

public class Main {
	static void calc_pressed(Stack<String> stack, String[] pressed) {
		int len = pressed.length;
		for(int i=0;i<len;i++) {
    		if(!pressed[i].equals(")"))
    			stack.push(pressed[i]);
    		else {
    			int cnt=0;
    			while(!stack.peek().equals("(")) {
    				String ele = stack.pop();
    				if(ele.equals("*"))
    					cnt+=Integer.parseInt(stack.pop());
    				else
    					cnt++;
    			}
    			stack.pop();
    			cnt*=Integer.parseInt(stack.pop());
    			stack.add(cnt+"");
    			stack.add("*");
    		}
    	}
	}
	static int get_length(Stack<String> stack) {
		int cnt=0;
		while(!stack.isEmpty()) {
			String tmp = stack.pop();
			if(tmp.equals("*"))
				cnt+=Integer.parseInt(stack.pop());
			else
				cnt++;
		}
		return cnt;
	}
	public static void main(String[] args) throws IOException {
        //선언 및 입력
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st;
    	StringBuilder sb = new StringBuilder();
    	String[] pressed = br.readLine().split("");
    	Stack<String> stack = new Stack<String>();
    	
    	//계산
    	calc_pressed(stack,pressed);
    	System.out.println(get_length(stack));
    	
    	
	}
} 

 

3) 재귀 풀이