기초 알고리즘 - 쇠막대기

레이저로 막대를 자르는 문제다.
()가 나오면 무조건 레이저를 표현한다.
문제를 직관적으로 생각해보면 '('가 3개면 쇠막대기 3개가 중첩된 것이다. 그리고 ()를 입력받으면 앞에 쌓인 '('의 수 만큼 절단한다.
ex) ()(((()())(())()))(())

• 여기서 (((는 쇠막대기 3개가 중첩된다.
• ()가 바로 나오므로 쇠막대기 개수에서 +3을 해줘 result = 6개가 된다.
• 그 후, 바로 ()레이저가 나오므로 result =9개가 된다.
• ')'로 인해 닫히므로 쇠막대기 개수는 2개가 된다.
• '('로 다시 쇠막대기가 하나 추가되어 3개로 늘어난다.
• 레이저가 관통했으므로 +3으로 result = 12다. 여기서, 예외가 있는데 쇠막대기가 새로 생기는 경우 두 조각으로 나뉘므로 +1을 해줘야한다.

위에서 바꿔줘야할게 있다. 초기 막대의 개수를 추가시키며 마지막에 더해주겠다.

나는 큐로 이 문제를 풀어보려했는데 두 조각이 나뉘는 경우를 구현하지 못했는데 스택으로 푸는 문제였다. 구현을보면 이걸 왜 못풀었는지 싶다. 너무 어렵게 생각하지 않고 직관적으로 풀어야겠다.

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


public class Hello_world {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str = br.readLine();
		
		StringBuilder sb = new StringBuilder();
		Stack<Character> stack = new Stack<>();
		
		int result =0;
		
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i) == '(') {
				stack.add('(');
			}
			if(str.charAt(i) == ')') {
				stack.pop();
				
				if(str.charAt(i-1) == '(') {
					result += stack.size();
				} else {
					result++;
				}
			}
		}
		
		System.out.print(result);
		
		}
}