[백준] 10799 : 쇠막대기 JAVA 풀이

 

 

문제를 읽고 어떻게 풀어야 하는지 전혀 감이 오지 않았다....

 

우선 문자열을 입력을 받는다.

 

문자열을 구성하는 문자는 '(' 또는 ')' 이다.

 

1. '('가 입력된 경우에는 스택에 push해준다.

 

2. ')'가 입력된 경우는 두 가지 케이스로 다시 나눠볼 수 있다.

    2-1. 이전 문자가 '('일 경우, 즉 레이저인 경우

            스택에 있던 '('를 pop하고 스택의 크기(= 쇠막대기의 개수)만큼 더해준다.

    2-2. 이전 문자가 ')'일 경우, 즉 한 막대기의 끝일 경우

            스택에 있던 '('를 pop하고 1을 더해준다. 

 

 

한 막대기의 끝을 나타내는 ')'일 경우 1을 더해주는 이유는 위 그림을 보면 이해가 갈 것이다.

그 막대는 더 이상 쪼개질 일이 없기 때문에 그 마지막 조각의 개수인 1을 더해주는 것이다.

 

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 문자열을 입력받음
		String str = br.readLine();
        // 문자열을 구성하는 문자들을 저장할 스택을 생성
		Stack<Character> s = new Stack<Character>();
		
        // 잘린 막대의 개수를 셀 변수
		int res = 0;
		
        // 입력받은 문자열의 길이만큼 반복
		for(int i=0;i<str.length();i++) {
        	// 문자열의 한 글자씩 읽음
			char c = str.charAt(i);
			
            // '(' 이라면 스택에 push
			if(c=='(') {
				s.push(c);
			}
            
			// ')' 이라면 
			else if(c==')'){
            	// 스택에 들어있던 '(' 를 pop
				s.pop();
                
                // 직전에 입력된 문자가 '(' 이었다면 == 레이저라면 
				if(str.charAt(i-1)=='(') {
                	// 스택의 크기(= 쇠막대기의 개수)만큼 더해줌
					res += s.size();
				}
                
                // 직전에 입력된 문자가 ')' 이었다면 == 한 막대기의 끝이라면
				else {
                	// 1을 더해줌
					res += 1;
				}
				
			}
		}
        // 잘린 막대기의 총 개수를 출력함
		System.out.println(res);
	}

}