9012 - 괄호[S4]

 

문제

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

9012번: 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다.

그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다.

 

만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

 

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

풀이

 

간단한 스택을 이용하는 문제. (, {, [ 등의 복잡한 로직의 경우도 하단에 같이 생각해보았다.

스택에 push할 때, 스택의 top에 있는 괄호와 현재 괄호의 종류에 따라 중첩 규칙을 확인해야 할 것이다.

스택의 top에 '['가 있고 현재 괄호가 '{'인 경우는 허용하지만, 반대의 경우는 허용하지 않는다.

코드

 

import java.util.*;
import java.io.*;
import java.io.*;
class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static void main(String[] args) throws IOException {
    	int N = Integer.parseInt(br.readLine());
    	while(N-- > 0) {
    		solve(); //메인 로직
    	}
    	bw.close();
    }
    
    public static void solve() throws IOException {
        String inputs = br.readLine();
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < inputs.length(); i++) {
            char c = inputs.charAt(i);

            if(c == '(') {
                stack.push(c);
            } else if(c == ')') {
                if(stack.isEmpty() || stack.peek() != '(') {
                    bw.write("NO\n");
                    return;
                }
                stack.pop();
            }
        }

        if(stack.isEmpty()) {
            bw.write("YES\n");
        } else {
            bw.write("NO\n");
        }
    }

}

 

//괄호가 여러 종류인 경우
import java.util.*;
import java.io.*;

class Main {

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

    public static void main(String[] args) throws IOException {
        int N = Integer.parseInt(br.readLine());
        while(N-- > 0) {
            solve();
        }
        bw.close();
    }

    public static void solve() throws IOException {
        String inputs = br.readLine();
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < inputs.length(); i++) {
            char c = inputs.charAt(i);

            if(c == '(' || c == '{' || c == '[') {
                if(!stack.isEmpty() && !isProperOrder(stack.peek(), c)) {
                    bw.write("NO\n");
                    return;
                }
                stack.push(c);
            } else {
                if(stack.isEmpty() || !isMatchingPair(stack.pop(), c)) {
                    bw.write("NO\n");
                    return;
                }
            }
        }

        if(stack.isEmpty()) {
            bw.write("YES\n");
        } else {
            bw.write("NO\n");
        }
    }

    private static boolean isMatchingPair(char opening, char closing) {
        return (opening == '(' && closing == ')') ||
               (opening == '{' && closing == '}') ||
               (opening == '[' && closing == ']');
    }

    private static boolean isProperOrder(char opening, char newOpening) {
        if(opening == '[' && newOpening == '{') return true;
        if(opening == '{' && newOpening == '(') return true;
        return false;
    }
}