[백준]BOJ 10799 쇠막대기

 

문제 조건

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

 

 

 

어려웠던 점

문제를 풀면서 여는 괄호와 닫는 괄호가 인접한 레이저인 경우에는 stack의 size만큼 더해주는 것은 생각을 했었습니다. 그러나, 그다음에 대해 생각해주지 못했습니다.

 

 

 

문제 풀이

왼쪽 끝은 여는 괄호 ‘ ( ’는 스택에 넣어줍니다.

레이저인 경우에는 쇠막대기가 잘립니다. 즉, 오른쪽 닫는 괄호 ')'인 경우 스택의 Top을 pop하여 레이저인 경우에는 스택 사이즈만큼 더해주면 됩니다. 

 

다음과 같이 레이저(빨갛게 칠해놓은 부분)를 만나는 경우 쇠막대기(노랗게 칠해놓은 부분)는 스택 사이즈만큼인 3개로 나뉘는 것을 확인할 수 있습니다.

 

 

닫힌 괄호가 레이저가 아닌 경우, 즉 쇠막대기인 경우 남은 잘린 부분을 더해주면 됩니다. 남은 잘린 부분은 +1 해주면 됩니다.

 

다음과 같이 쇠막대기의 닫힌 괄호(빨갛게 칠해놓은 부분)을 만난 경우 남은 쇠막대기(파랗게 칠해놓은 부분)는 +1 해주면 되는 것을 확인할 수 있습니다. 

 

 

 

문제 구현

public class Main_10799 {
	public static void main(String[] args) throws IOException {
		Stack<Character> stack = new Stack<>();
		int result = 0;

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();

		for (int i = 0; i < str.length(); i++) {
			if (str.charAt(i) == '(') {
				stack.add(str.charAt(i));
			} else {
				if(stack.pop() == i-1) result += stack.size();//레이저인 경우
				else result++;//쇠막대기인 경우
			}
		}

		System.out.println(result);
	}

}