[백준/자바] 11899번 괄호 끼워넣기

 

 

 

풀이

스택을 하나 생성한 후 문자열 길이만큼 반복한다.

• ')'를 만난 경우
  • 스택이 비어있거나, 스택의 제일 상단값이 ')'이면 짝 괄호가 없다는 뜻이므로 '(' 괄호가 필요하다. 따라서 count를 1 증가시킨다.
  • 그렇지 않다면 (스택이 비어있지 않고, 스택의 제일 상단값이 '(' 이면) 짝 괄호가 있다는 뜻이므로 스택을 pop 한다.
• '('를 만난 경우
  • 무조건 push 한다.

 

 

반복문이 끝난 후 '('만 남아있거나 스택이 비어있을 것이다.

따라서 마지막에 스택의 크기(size)만큼 count에 더해준다.

 

 

 

 

 

코드

package baekjoon._11899;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;

public class Main {

    public static int solution(String str) {

        int count = 0;

        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < str.length(); i++) {

            char current = str.charAt(i);

            if(current == ')') {
                if (stack.isEmpty() || stack.peek() == ')') {
                    count++;
                }
                else {
                    stack.pop();
                }
            }

            else { // '('
                stack.push(current);
            }

        }

        count += stack.size();

        return count;

    }
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        String str = br.readLine();

        bw.write(sb.append(solution(str)).toString());
        bw.flush();

        bw.close();
        br.close();
    }
}