[백준 1662] 압축 (Java)

문제 링크: https://www.acmicpc.net/problem/1662

1662번: 압축

1. 주의할 점

- 괄호에 대한 처리

- 문자열을 복원 v.s 길이만 구하기

 

2. 구현

- 문자열을 복원하지 않고 길이만 구해도 되므로, 길이만 구하여 메모리 또한 아낄 수 있도록 한다. 다만, 구현이 좀 더 복잡 할 수 있다

- Stack 2개를 이용하여 해결한다

#예시
234(10)

- Len 스택에는 '(' 괄호가 나오기 전의 숫자를 제외하고 계산된 길이. 위의 예시에선 '23'이 해당하므로 길이 2를 저장

- Mul 스택에는 '(' 괄호 직전에 나온 숫자를 저장. 위의 예시에선 '4'가 해당하므로 4를 저장

- 위의 설명이 부실하기에 아래 몇 개의 TC를 예로 들겠습니다 

#TC 1
11(00)9

Len: push(1) -> pop()
Mul: push(1) -> pop()

#TC 2
22(234(01)1)

Len: push(1) -> push(2) -> pop() -> pop()
Mul: push(2) -> push(4) -> pop() -> pop()

#TC 3
33(562(71(9)22)2)

Len: push(1) -> push(2) -> push(1) -> pop() -> pop() -> pop()
Mul: push(3) -> push(2) -> push(1) -> pop() -> pop() -> pop()

- Cnt를 0으로 초기화하고 문자열을 좌에서 우로 순차적으로 검사한다

- 문자열에서 숫자가 나오면 Cnt++, '('가 나오면 Cnt를 계산하여 Len과 Mul 스택에 값을 추가한다. ')'가 나오면 Mul과 Len 스택에서 원소를 뽑아서 계산하고 Cnt에 할당한다

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

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine().trim();
	    Stack<Integer> len = new Stack<>();
	    Stack<Integer> mul = new Stack<>();
	    
	    int cnt=0;
	    for(int i=0;i<str.length();i++){
	        char c = str.charAt(i);
	        if(c=='('){
	            cnt-=1;
	            int mulNum = str.charAt(i-1)-'0';
	            len.add(cnt);
	            mul.add(mulNum);
	            cnt=0;
	        }
	        else if(c==')'){
	            int val = mul.peek();
	            mul.pop();
	            val*=cnt;
	            int plus = len.peek();
	            len.pop();
	            cnt = plus + val;
	        }
	        else  cnt++;     //숫자
	    }
		System.out.print(cnt);
	}
}