10799_ <쇠막대기>

10799번: 쇠막대기 (acmicpc.net)

10799번: 쇠막대기

 

닫는 괄호와 여는 괄호를 중심으로 문제를 해결해야하는 문제. - 이 괄호 꺾쇠를 보면 이젠 습관적으로 스택을 떠올리게 된다.

이 문제 역시 스택으로 풀었어야했다.

난 처음에 어느 괄호를 기준으로 잡아야할지 감이 안와서 잘 못 풀었었다. 

뭐 크게 경우는 두가지 이지만, 연속될 경우를 잘봐야 한다.

 

접근.

1.

 

(( / () / )) / )( / 총 4가지의 연속경우가 있으니 이를 잘 참고해야겠다. ()인 경우 레이저를 표시하기에 이 포인트가 중요할것 같다하고 경우를 나눠보자.

 

2.

여기서 ((는 쇠막대기의 시작이라고 생각하면 )의 쇠막대기의 끝이다. 여기서 뭔가 할일이 더 많아보인다. 

따라서 )을 기준점으로 잡는게 첫번째 올바른 방향이다.

 

3. 조건 만들기

1. ( 일때

걍 단순하게 스택에다 (만 추가해도 될 것같다. 근거는 ((이게 아무리 생겨도 그냥 쇠막대기가 계속 늘어나는 것이기에 크게 할 수 있는게 없다.

 

 

2. )일때 

이때는 1과는 다르게 ) 이전의 인덱스에 집중을 해야한다.

 

#1. ()일 경우 - 이는 레이저 이다. 1에서 쌓아놓은 쇠막대기를 반으로 자르기에 1에서 쌓아놓은 녀석만큼 조각이 생겨나겠다. ((( () ))) 일 경우 3+3 6조각이 나겠다.

일단 (((으로 stack =3이 된다. 여기서 (에서 stack이 4며 )를 만났을때는 stack을 하나 먼저 (pop)빼줘야한다. ()는 레이저이지 쇠막대가 아니니까. 

그리고 한번 stack에서 뺀 만큼의 size을 ans에다가 더해준다.

 

 

#2. ))일 경우 - 이땐 일단 하나의 쇠막대기가 끝이난거기에 stack에서 (를 pop해야겠다는건 자연스럽다.

 

하지만 좀 헷갈리는 부분은 조각을 몇개 추가해야하나? 이것이었다 나는.

 

((( () ))) 의 경우를 보자. 

 

((( () 를 지나고 ) 일 경우이다. 현재 stack=3이며 ans=3이다.  2번째 )는 사실 세번째 ( 의 엔딩포인트이니 레이저가 잘렸을때 가장 작은 쇠막대기의 반쪽 조각이다.

따라서 잘린 조각 하나를 추가하면 되겠다. 즉 ans++; % stack.pop().

 

• 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.
• 각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.
• 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.

이 3가지의 조건 때문에 사실 저 2가지의 조건문만으로 stack의 (를 다 pop이 가능해서 추가적인 isempty는 검사 안해도됌!

까지 알면 깔끔하겠다.

import java.io.*;
import java.util.*;

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();
		int metal = 0;
		Stack<Character> stack = new Stack<>();
		for(int i=0; i<str.length(); i++) {
			if(str.charAt(i)=='(') {
				stack.push('(');
			}
			else {
				//))
				if(str.charAt(i-1) == ')') {
					if(!stack.isEmpty()) {
						stack.pop();
						metal++;
					}
					
				}
				//()
				else if(str.charAt(i-1) == '(') {
					stack.pop();
					metal= metal+stack.size();
					
				}
			}
		}
		System.out.println(metal);
		 	
	}

}