백준 - 괄호 끼워넣기 ( 11899번, JAVA )

Stack ( https://www.acmicpc.net/problem/11899 )

풀이

• 만약 스택이 비어있는데 ")" 가 먼저 온다면 왼쪽부분 미완성 카운트+1
• "(" 여는 괄호가 온다면 스택에 push
• 만약 스택에 최상단이 여는 괄호이고 다음 오는 괄호가 닫는 괄호라면 괄호 완성해서 스택에서 빼내기
• 여는 괄호가 온다면 그대로 스택에 push
• 마지막으로 남은 여는 괄호만큼 오른쪽에 닫는 괄호가 필요하므로 카운트한 cnt + 스택에 사이즈 == answer
• 스택에 성질을 이용하면 정말 쉬운 문제😎

package problem_solving.stack;

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

public class BaekJoon_11899 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String [] s = sc.next().split("");
//		System.out.println(Arrays.toString(s)); [), ), ), (, )]
		Stack<String> st = new Stack<>();
		int cnt = 0 ;
		for(int i = 0 ; i < s.length; i++) {
			if( st.isEmpty()) {
				if( s[i].equals(")")) {
					cnt++;
				} else {					
					st.push(s[i]);
				}
			} else {
				if(st.peek().equals("(") && s[i].equals(")")) {
					st.pop();
				} else if( st.peek().equals("(") && s[i].equals("(")){
					st.push(s[i]);
				}
			}
			
		}
		System.out.println(cnt+st.size());
		
	}

}