[백준] 11899번 : 괄호 끼워넣기 – JAVA [자바]

 

https://www.acmicpc.net/problem/11899

11899번: 괄호 끼워넣기

 

 

---

 

• 문제

---

• 문제 풀이

백준 11899번 괄호 끼워넣기는 스택을 이용해서 푸는 문제이다. 스택 이론을 공부하고 싶으면 밑에 있는 링크를 참고하면 되겠다.

 

https://propercoding.tistory.com/entry/자료구조-스택Stack

[자료구조] 스택(Stack)

이 문제에서는 올바르지 않은 괄호열 S가 주어지고 올바를 괄호열으로 만들기 위해 앞과 뒤에 붙여야 할 괄호의 최소 개수를 구하면 된다.

 

이 문제를 푸는 방법을 보겠다.

일단 올바르지 않은 괄호열 S의 첫 인덱스를 스택에 push 한다.

stack.push(s.charAt(0));

그리고 올바르지 않은 괄호열 S를 인덱스 1부터 iterate 한다. 

char c = s.charAt(i);

두 가지의 경우로 나눌 수 있다.

1) c == ' ( '

2) c == ' ) '

 

경우 1)  c == ' ( ' 

만약에 c == ' ( ' 이면 스택에 push 한다.

 

경우 2)  c == ' ) '

만약에 c == ' ) '이고 스택에서 맨 위에 있는 게 ' ( '이면 스택에서 pop 한다.

if (stack.size() > 0 && stack.peek() == '(') stack.pop();

스택이 비어있거나 스택 맨 위가 ' ( '가 아니면 스택에 push 한다.

---

• 코드

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        Stack<Character> stack = new Stack<>();
        stack.push(s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.size() > 0 && stack.peek() == '(') {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        System.out.print(stack.size());
    }
}

 

---

• 후기

백준 11899번은 스택 문제를 많이 안 풀어봤으면 어려울 수도 있는 문제인데 스택 문제를 조금 풀어봤으면 쉽게 접근할 수 있는 문제이다.