백준 10799번: 쇠막대기 [스택][Stack][누적합] -Java

 

상세 풀이는 코드상에 주석으로 달아두었다.

누적합+스택을 이용하였다.

누적합 없이 레이저 관점에서 레이저 생성시점에 열려있는 쇠막대기들을 모두 자르는 방법도 있다.

 

<Java코드>

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();

		Stack<Integer> stack = new Stack<Integer>();

		int[] rsum = new int[100000];
		int res = 0;

		if (str.charAt(0) == '(') {
			stack.push(0);
		}

		for (int i = 1; i < str.length(); i++) {
			char ch = str.charAt(i);

			if (ch == '(') {
				// 여는괄호가 나오면 idx를 스택에 저장
				stack.push(i);
				rsum[i] = rsum[i - 1];

			} else {
				// 레이저 판별은 스택의 peek가 현재 idx과 1차이 나는지?\
				// 레이저가 맞다면 레이저 갯수 누적합 배열에 +1
				if (i - stack.peek() == 1) {
					stack.pop();
					rsum[i] = rsum[i - 1] + 1;
				} else {
					// 아니면 이전 누적합 숫자 그대로 이어갈것, 쇠막대기 만들어진 것으로 간주

					rsum[i] = rsum[i - 1];
					// 쇠막대기 길이구간 사이에 존재하는 레이저 갯수 파악하여 자른 조각 cnt
					int start = stack.pop();
					int sidx = start <= 0 ? 0 : start - 1;
					res += rsum[i]-rsum[sidx]+1;
					
				}
			}
		}
		
		System.out.println(res);

	}

}