[백준 10799] 쇠막대기

문제

10799번: 쇠막대기

문제풀이

이런 문제를 처음 보면 막막하다. 그럴때는 하나씩 써내려가면서 경우를 나눠서 생각. 

 

1) 상황분류

 - ( 이 나오는 경우: 가능성이 두가지다. 레이저가 될 수도 있고 막대기의 시작이 될 수도 있다. 레이저가 되는 경우는 다음에 오는 괄호가 )인경우이고 막대기의 시작이 되는 경우는 다음에 오는 괄호가 (인 경우이다

 

 - ) 이 나오는 경우: 마찬가지로 두가지의 가능성이 있는데, 전에 나온 괄호가 )인경우 막대기의 끝이되고, ( 인 경우 레이저가 된다. 

 

 여기까지 상황에 대한 분류를 나눴으니 각 상황을 좀 더 구체화 해보자

 

2) 구체화

레이저가 나오는 경우는 두가지인데 ( 에서 레이저를 판단하거나 ) 에서 레이저인지를 판단하는 경우다. 여기에서는 ( 에서 레이저인 경우를 판단하고 인덱스를 하나 증가시켜 ) 를 중복 검사하지 않도록 한다.

 

그럼 이제 count에 대한 부분만 남았다. '언제'count를 하는 지를 알았으니 '어떻게 count할지를 보자. 

3) 실행

- 레이저가 나오는 경우: 현재까지 남아있는 (의 수. 즉 스택의 사이즈를 더한다

- 막대기의 끝: 막대기가 끝나고 하나의 조각이 생겼으므로 count +1 을 해준다. 

 

 

소스코드

import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		String parenthesis =in.next();
		Stack<String> stack=new Stack<String>();
		int count=0;
		
		for(int i=0;i<parenthesis.length();i++) {
			char presentP=parenthesis.charAt(i);
			char nextP=' ';
			char beforeP=' ';
			if(i<parenthesis.length()-1) {
				nextP=parenthesis.charAt(i+1);
			}
			if(i>0) {
				beforeP=parenthesis.charAt(i-1);
			}
			
			if(presentP=='(') {
				if(nextP=='(') {
					stack.push("(");
				}
				else {
					//()이므로 레이저
					count+=stack.size();
					i+=1;
				}
			}
			else {
				// )인경우 막대기의 끝 
				stack.pop();
				count+=1;
			}	
		}
		System.out.println(count);
	}
}