[백준] 10799번 : 쇠막대기

문제

주어진 쇠막대기들에 레이저를 발사했을 때 쇠막대기가

총 몇 개로 나뉘는지 계산하는 문제

 

접근 방식

풀고 나니 엄청 간단했지만 풀이법을 알기까지 많은 시간이 걸린 문제로

코드를 보면 알겠지만 엄청 간단한 문제다.

 

()(((()())(())()))(())

위와 같은 문자열이 주어졌을 때

괄호가 열리자마자 닫히면 레이저고

그렇지 않다면 쇠막대기라는 것을 알 수 있다.

 

쇠막대기의 양끝과 레이저는 겹치지 않기 때문에

쇠막대기 위에 레이저가 발사되면 무조건 쇠막대기가 잘라진다.

 

즉 레이저를 쐈을 때 현재 스택에 있는 쇠막대기의 수만큼

쇠막대기가 늘어나기 때문에

열리자마자 닫히는 괄호를 발견했을 때마다

스택의 사이즈만큼 더해주면 된다.

 

주의해야 할 점은 쇠막대기가 끝날 때도 1씩 더해줘야 하는데

길이가 3인 쇠막대기를 2번 자르면 3개가 되기 때문이다.

 

이해가 어렵다면 아래 과정을 참고하길 바란다

 

()(((()())(())()))(())

레이저 +0
막대기 1
막대기 2
막대기 3
레이저 +3
레이저 +3
막대기 2 +1
막대기 3
레이저 +3
막대기 2 +1
레이저 +2
막대기 1 +1
막대기 0 +1
막대기 1
레이저 +1
막대기 0 +1 

총 17조각

 

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		char[] input = br.readLine().toCharArray();

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

		int count = 0;

		for (int i = 0; i < input.length; i++) {
			if (input[i] == '(') {
				stack.push(input[i]);
			} else if (input[i - 1] == '(' && input[i] == ')'){
				stack.pop();
				count += stack.size();
			} else {
				stack.pop();
				count++;
			}
		}

		System.out.println(count);
	}
}