[백준] 1662번 : 압축(JAVA)

https://www.acmicpc.net/problem/1662

1662번: 압축

풀이

일단 String을 계속 선언하면서 하면 최종적으로 메모리초과가 뜹니다.

문제는 최종 문자열을 출력하는게 아닌 문자열의 길이를 출력하는거니 길이체크만 해주면 되서 long으로 해주면됩니다.

 

stack을 활용하여 )가 나올 시 (까지 count를 세줍니다.

여기서 *(count를 세준 후 나온 값을 *과함께 넣어줌)이 나올 경우 그값을 그대로 더해줍니다. 아닌경우 +1

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		
		Stack<String> stack = new Stack<>();
		for(char ch : br.readLine().toCharArray()) {
			if(ch != ')') {
				stack.add(ch + "");
			}
			else {
				int count = 0;
				while(!stack.peek().equals("(")) {
					count += stack.pop().equals("*") ? Integer.parseInt(stack.pop()) : 1;
				}
				stack.pop();
				
				stack.push(String.valueOf(count * Integer.parseInt(stack.pop())));
				stack.push("*");
			}
		}
		
		long answer = 0;
		while(!stack.isEmpty()) {
			answer += stack.pop().equals("*") ? Integer.parseInt(stack.pop()) : 1;
		}
		
		System.out.print(answer);
	}
}