10799 : 쇠막대기 ( 백준 / java )

www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

 

 

* 풀이 과정

이 문제는 괄호에 관한 문제이기 때문에 stack을 이용해야겠다는 생각을 했습니다. 그리고 막대를 자르는데, 계층마다 수가 늘어나기 때문에 '('가 증가할 때마다 변수를 같이 증가시켰습니다. 혹시 여러분 예시문제 2개가 제대로 맞지 않는다면 '()' '(())' '(()())' 와 같은 비슷하지만 간단한 케이스를 만들어보고 한번 테스트해보기 바랍니다. 테스트를 만들어서 반례를 찾는 것도 실력입니다. 가끔 너무 작은 데이터, 터무니 없는 큰 데이터, 한쪽으로 쏠린 데이터 등 문제가 제대로 풀리지 않으면 다양한 테스트 케이스를 만들고 시도해보도록 합니다.

 

저도 처음에 이 문제를 풀 때, 1번 예시는 제대로 맞았지만 2번 문제는 틀렸습니다. 그래서 반례를 찾으면서 위의 괄호들을 입력해 보았고 '(()())'가 답이 3이지만 저는 2를 출력하며 문제점을 찾았습니다. 괄호가 끝나는 시점에서 그 이전에 있는 괄호가 무엇인지에 따라 갯수가 변한다는 것을 알 수 있었습니다. 그래서 ')' 바로 직전에 나온 괄호가 '('인지 ')'인지 나누어서 계산하도록 수정하여 맞았습니다.

 

다시한번 말하지만 적절한 반례를 찾아 문제점을 발견하는 것도 실력입니다. dp에서도 가끔 n이 1,2일 때 아예 오류를 출력하는 경우가 있을 것입니다. 혹은 너무 큰 숫자를 입력하면 터져버리는 경우도 있을 것입니다. 반례를 검색하고 테스트케이스를 얻어 해결하는 것도 대단한 일이지만 그 전에 스스로 만들어보고 고민해보면 훨씬 문제를 접근하는 시야를 기르는데 도움이 많이 될 것입니다.

 

package bj;

import java.util.*;
public class Main {

	static String line="";
	static int answer=0;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		line = sc.nextLine();
		int start=0;
		
		Stack<Character> stack = new Stack<>();
		for(int i=0;i<line.length();i++) {
			char c = line.charAt(i);
			if(c=='(') {
				stack.push('(');
				start++;
			} else {
				start--;
				if(line.charAt(i-1)=='(') {
					answer+=start;
					stack.pop();
				} else {
					answer++;
					stack.pop();
				}
			}
		}
		System.out.println(answer);
	}
}