[실버4] BOJ 9012 괄호

요구사항

입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

문제 분석

• 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다.
• x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다.
• 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다.
• 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다.
• 입력은 T개의 테스트 데이터로 주어진다.
• 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다.
  (*BufferReader 사용 → 입력 문자열의 길이가 길거나 테스트 케이스가 많을 경우, Scanner보다 BufferedReader가 입출력 성능 면에서 훨씬 빠르기 때문.)

손으로 풀기

[1차]

1. 테스트 데이터를 받을 때마다 String에 저장
2. 1번마다 String을 순회하며 “(”와 “)”를 count한다.
3. “(”와 “)”의 카운트가 일치 하지 않는다. → NO, 일치한다 → YES

‼️ ())(() → 개수는 맞는데 VPS가 아님

[2차]

1. “(”를 만나면 “(”를 Stack에 push(Stack은 LIFO → History = “)”를 만났을 때 직전에 “(”가 있냐
2. “)”를 만나면 기존에 Stack을 그저 pop → 이 때 요소를 찾을 수 없다면 NO
3. 1번과 2번을 문자열이 끝날 때까지 반복함
4. “(”이 남아있다면 → NO
5. 그게 아니라면 Yes 정상종료

Sudo code

[1차]

BufferReader br;

테스트 데이터 개수 N

for(N만큼 반복){
	String 입력문자열 = br.readLine()
	for(입력문자열 순회){
		if("(") 열린괄호++;
		if(")") 닫힌괄호++;	
	}
	if(열린괄호 == 닫힌괄호) "Yes" 출력
	else "No" 출력
}

[2차]

BufferReader br; 테스트 데이터 개수 N 
Stack<Character> stack; 

for(N만큼 반복){ 
String 입력문자열 = br.readLine() 

for(char ch : 입력문자열.toCharArray()){
	 if(ch == '(') stack.push(ch); 
	 else if(ch == ')') stack.pop(); 
 } 
 
 if(스택의 마지막 요소 == '(') No 출력 
 else Yes 출력 
 

Code

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

public class BOJ9012 {

    public static String solve(String ps) {
        Stack<Character> stack = new Stack<>();

        for (char ch : ps.toCharArray()) {
            if (ch == '(') {
                stack.push(ch);
            }
            else if (ch == ')') {
                // 닫는 괄호인데 스택이 비어 있으면, 짝이 없으므로 바로 NO
                if (stack.isEmpty()) {
                    return "NO";
                }
                // 짝이 있으므로 pop
                stack.pop();
            }
        }

        // 문자열 순회가 끝난 후 최종 검사
        // 스택이 완전히 비어있어야 VPS (YES)
        if (stack.isEmpty()) {
            return "YES";
        } else {
            // 스택에 여는 괄호가 남아 있으면 VPS 아님 (NO)
            return "NO";
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder(); // 출력을 모으기 위한 StringBuilder

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            String ps = br.readLine();
            sb.append(solve(ps)).append('\n');
        }

        System.out.print(sb);
    }
}