[백준/9012] 괄호 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/9012
• 분류 : 자료구조, 문자열
• 풀이 시간 : 10분

문제 해설

1. 괄호 문자열 = '('와 ')'로만 이루어진 문자열
2. 올바른 괄호 문자열 = 괄호의 모양이 바르게 구성된 괄호 문자열
   1. 괄호가 열린만큼 닫혀야 한다 = 짝맞춰서 이루어져야함
   2. 닫을 괄호가 없는데 닫으면 안됨
3. 입력으로 주어진 괄호 문자열이 올바른 괄호 문자열인지 판단

Solution

풀이 접근 방법

1. 괄호 문제 = 스택 사용
   1. 스택 = 여는 괄호만 담아져있음
   2. 여는 괄호 = 스택에 넣음, 닫는 괄호 = 스택에서 여는 괄호 뽑아서 정상적인 괄호로 판별

정답 코드

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 void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.valueOf(br.readLine());
        StringBuilder answer = new StringBuilder();

        while (T-- > 0) {
            String s = br.readLine();
            if (checkYps(s))
                answer.append("YES\n");
            else
                answer.append("NO\n");
        }

        bw.write(answer.toString() + "\n");
        bw.flush();
        bw.close();

    }

    public static boolean checkYps(String s) {
        char[] sArr = s.toCharArray();
        Stack<Character> vps = new Stack<Character>();

        // VPS가 되기 위해서 무조건 여는 괄호로 시작해야한다
        if (sArr[0] == ')')
            return false;

        for (int i = 0; i < sArr.length; i++) {
            // 여는 괄호일 경우 스택에 넣음
            if (sArr[i] == '(')
                vps.add(sArr[i]);
            else {
                // 닫는 괄호가 나왔을 경우 괄호의 짝을 맞추기 위해 stack에서 뽑음
                // 하지만 스택이 비어있는 경우 뽑으면 에러
                // 스택에 비어있음 = 이전까지는 모든 괄호가 짝 맞춰 있음
                if (vps.isEmpty())
                    return false;
                vps.pop();
            }

        }

        if (vps.isEmpty())
            return true;
        else
            // 스택이 비어있지 않음 = 열려있는 괄호 존재
            return false;
    }
}