쇠막대기 절단 문제 (Stack)

 

 

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

public class Main {

	public int solution(String str) {
		int ans = 0;
		
		Stack<Character> stk = new Stack<>();
		for(int i = 0; i < str.length(); i++) {
			char temp = str.charAt(i);
			
			if(temp == ')'){
				if(str.charAt(i-1) == '(') {
					stk.pop();
					ans += stk.size();
				}
				else if(str.charAt(i-1) == ')') {
					ans++;
					stk.pop();
				}
			}
			else if(temp == '(') stk.push(temp);

		}
		return ans;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main T = new Main();
		Scanner kb = new Scanner(System.in);

		String str = kb.next();
		System.out.println(T.solution(str));
	}

}

 

• ( → 막대기 추가
  • push
• ( ) → 절단
  • answer += 현재 막대 개수
• ) ) → 막대기 끝
  • answer +=1

 

 

 

출처 : 한국정보올림피아드