1662_압축 (JAVA)

1662번: 압축

import java.util.Scanner;
import java.util.Stack;

public class Main {
	static String S;
	static Stack<Integer> stack = new Stack<>();
	static int[] close;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		S = sc.next();
		
		/*
		괄호 시작,끝의 위치를 close[]배열에 저장한다.
		1. 괄호 시작 위치를 스택에 push 하고,
		2. 이후에 괄호 끝을 만나게 되면, 스택에서 pop
		   close[시작위치]=끝위치 로 저장한다.
		 */
		
		close = new int[S.length()];
		for(int i=0; i<S.length(); i++){
			if(S.charAt(i)=='(')
				stack.push(i); //괄호시작 위치 스택에 push
			if(S.charAt(i)==')'){
				int start = stack.peek();
				stack.pop();
				close[start] = i;
			}
		}
		
		System.out.println(cal(0, S.length()));
	}
	private static int cal(int start, int end){
		/*
		입력받은 string을 0~string.length()까지 하나씩 증가하며 탐색한다.
		이때 두 가지의 경우로 나누어 수행한다.
		1. 현재 위치 i가 괄호시작 이라면,
		   i-1번째 위치의 숫자 * (i+1 부터 i번째 위치의 괄호끝 위치 까지 다시 수행)
           만큼 ans에 더한다.
		2. 현재 위치 i가 숫자 라면,
		   1에서 현재 위치가 괄호 안으로 들어왔을 때 수행된다.
		   즉, 괄호 안의 숫자 개수를 세어주며, 
           이를 반환하여 괄호 시작 전에 위치한 숫자를 곱한다.
		   
		예를 들면, 33(562(71(9))) 입력받을 때를 보자.
		  close[2]=13, close[6]=12, close[9]=11 이 되고,
		  cal(0,14) -> ans += 3*cal(3,13) = 2+3*6-1 = 19
		  cal(3,13) -> ans += 2*cal(7,12)-1 = 1+2*1-1 = 2
		  cal(7,12) -> ans += 1*cal(10,11)-1 = 1+1*1-1 = 1
		  cal(10,11) = 1
		로 최종 출력은 19가 된다.
		*/
		
		int ans=0;
		for(int i=start; i<end; i++){
			if(S.charAt(i)=='('){
				int num = S.charAt(i-1)-'0';
				
				ans += num * cal(i+1, close[i])-1;
				i = close[i];
			}
			else
				ans++;
		}
		return ans;
	}
}

 

스택 이용해서 풀었던 첫 번째 문제! 어떻게 스택을 사용해야되는지를 몰라몰라몰라서 한참 걸렸다ㅠㅠ 헝 어려워

 

 

타 블로그 정보에 따르면!

문자열 압축, 괄호 문제는 스택을 이용한다고 한다. 기억해둬야지..!