[백준] 9012번 괄호 (Java)

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

9012번: 괄호

---

문제

---

알고리즘

 

이번 문제는 Stack을 사용해서 문제를 풀어야 한다! 

Java에는 java.util.Stack 클래스가 있어서 쉽게 stack을 사용해서 문제를 풀 수 있다. (나는 처음으로 사용하는거라 약간 설렌다)

 

Stack 클래스를 사용하는 방법은 다음과 같다.

 

1. Stack 선언

Stack <Integer> stackInt = new Stack<>();
Stack <Character> stackChar = new Stack<>();

 

<> 사이에 원하는 데이터 타입을 넣으면 된다.

 

2. add(), push() : 값 추가

stackInt.push(1);
stackInt.add(2);

 

3. pop() : 마지막 값 삭제

stackInt.pop();

 

4. clear() : 내용 모두 삭제

stackInt.clear();

 

5. peek() : 마지막 값 출력

stackInt.peek();

 

6. empty() : 비어 있는지 확인 (return value : true / false)

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

stack.push(1);
stack.push(2);
stack.push(3);

stack.pop(); // 3 삭제
stack.pop(); // 2 삭제

System.out.println(stack.empty()); // false

stack.pop(); // 1 삭제

System.out.println(stack.empty()); // true

 

7. search() : 내용 검색 (return value : index)

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

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(1);

System.out.println(stack.search(2)); // 3 => 인덱스 값
System.out.println(stack.search(1)); // 1 => 가장 최근 값
System.out.println(stack.search(4)); // -1 => 값 없음

 

---

다시 돌아와서 문제의 해결 방법을 설명하자면,

 

1. String인 PS를 입력받는다.

2. PS의 한 문자씩 검사할 때, 

• '(' 면, stack에 push()
• ')'면서 stack에 비어있지 않다면, stack에서 pop()
• ')'면서 stack이 비어있다면, "NO" 출력

3. PS 끝까지 검사하고 stack이 비어있면, "YES"

4. stack에 내용이 남아있다면, "NO"

 

---

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine()); // 데이터 개수
        for(int i=0; i<T; i++) {
            String ps = br.readLine();

            bw.write(isVPS(ps) + "\n");
        }

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

    // VPS인지 판단하는 함수
    public static String isVPS(String ps) {
        Stack<Character> stack = new Stack<>();

        for(int i=0; i<ps.length(); i++) {
            char psChar = ps.charAt(i);

            if(psChar == '(') { // '(' 일때, stack에 추가
                stack.push(psChar);
            }
            else if(psChar == ')' && !stack.empty()) { // ')' 이면서 stack에 내용이 있다면, pop
                stack.pop();
            }
            else if(psChar == ')' && stack.empty()) { // ')' 인데 stack이 비어있다면, NO
                return "NO";
            }
        }

        if(stack.empty()) {
            return "YES";
        } else {
            return "NO";
        }
    }
}