BOJ 9012 괄호

By kuper0201

Published in 알고리즘

2021-03-05

1 min read

문제

입력

풀이

문제

BOJ 9012 괄호 바로 가기

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다.
그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다.
한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다.
만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다.
예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다.
입력은 T개의 테스트 데이터로 주어진다.
입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다.
각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다.
하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

풀이

해당 문제는 복잡해 보이지만 사실 여는 괄호 '('와 닫는 괄호 ')'의 쌍이 정확한지를 판별하라는 문제이다.

문제를 풀기에 앞서 괄호들이 쌍을 이루기 위한 몇 가지 조건들을 알아둘 필요가 있다.

문제에서 제시한 예시를 보면 "(()("와 같은 경우에는 여는 괄호는 3개, 닫는 괄호는 1개로 개수가 맞지 않아 올바른 괄호 쌍이 생성되지 않는다.

또한, VPS를 다른 VPS에 넣거나 접합시켜 새로운 VPS를 생성하므로 ")("와 같은 VPS는 존재 할 수 없다는 것을 알 수 있다.

위의 예시들을 통해 여는 괄호와 닫는 괄호가 같은 개수만큼 순서대로 존재해야 한다는 VPS의 첫 번째 조건이 도출된다.

하지만 VPS의 두 번째 조건은 조금은 직관적이지 않다.

문제에서 제시한 예시인 "(())()"의 괄호 쌍을 각각 다른 색으로 칠하면 아래와 같은 결과를 확인 할 수 있다.

(())()

색칠한 결과를 살펴 보면 하나의 괄호 쌍은 항상 최소의 거리를 가진다는 것을 알 수 있다.

쉽게 말하자면 "닫는 괄호는 언제나 가장 마지막에 나온 여는 괄호에 대응된다"라는 말이다. 이를 통해 LIFO(Last In, First Out) 구조를 떠올릴 수 있다.

대표적인 LIFO 구조를 갖는 자료구조는 Stack이므로 해당 문제는 Stack 자료 구조를 응용하면 쉽게 해결이 가능하다.

Stack을 이용한 로직은 다음과 같다.

주어진 문자열을 순회하며 여는 괄호를 스택에 추가한다.
닫는 괄호가 나올 경우 스택의 마지막 값이 여는 괄호인지 확인한다.
여는 괄호일 경우 괄호 쌍이 생성되므로 스택에서 제거하고 반복한다.
여는 괄호가 아닐 경우 괄호 쌍이 생성되지 않으므로 non-VPS 판별.
모든 반복 종료 후 스택이 비어있지 않으면 닫히지 않은 괄호가 존재하므로 non-VPS 판별.

코드 보기(Java)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stk = new Stack<>();

        // 테스트 케이스 개수 입력
        int N = Integer.parseInt(br.readLine());
        for(int i = 0; i < N; i++) {
            // 괄호 문자열 입력
            String str = br.readLine();
            boolean isVPS = true;
            stk.clear();

            for(int j = 0; j < str.length(); j++) {
                char ch = str.charAt(j);

                if (ch == '(') {
                    // 스택에 여는 괄호 추가
                    stk.push(ch);
                } else if (ch == ')') {
                    // 스택이 비었거나 여는 괄호가 아니라면 VPS가 아님
                    if(stk.isEmpty() || stk.peek() != '(') {
                        isVPS = false;
                        break;
                    }

                    // 스택이 비어있지 않고, 여는 괄호 일 경우 스택에서 제거
                    stk.pop();
                }
            }

            // 전부 순회 하였는데 스택 비어있지 않으면 VPS가 아님
            if(stk.size() != 0) isVPS = false;

            if(isVPS) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

코드 보기(C++)

#include <iostream>
#include <stack>

#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define endl '\n'

using namespace std;

int main() {
    fastio;
    
    // 테스트 케이스 개수 입력
    int N;
    cin >> N;
    
    stack<char> stk;
    for(int i = 0; i < N; i++) {
        // 괄호 문자열 입력
        string str;
        cin >> str;
        bool isVPS = true;
        while(!stk.empty()) stk.pop();
        
        for(int j = 0; j < str.length(); j++) {
            char ch = str[j];

            if (ch == '(') {
                // 스택에 여는 괄호 추가
                stk.push(ch);
            } else if (ch == ')') {
                // 스택이 비었거나 여는 괄호가 아니라면 VPS가 아님
                if(stk.empty() || stk.top() != '(') {
                    isVPS = false;
                    break;
                }

                // 스택이 비어있지 않고, 여는 괄호 일 경우 스택에서 제거
                stk.pop();
            }
        }
        
        // 전부 순회 하였는데 스택 비어있지 않으면 VPS가 아님
        if(stk.size() != 0) isVPS = false;

        if(isVPS) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    
    return 0;
}

코드 보기(Kotlin)

import java.util.*;

fun main(args: Array<String>) {
    val stk = Stack<Char>()
    
    // 테스트 케이스 개수 입력
    var N = readLine()!!.toInt()
    for(i in 0 until N) {
        // 괄호 문자열 입력
        var str = readLine()!!
        var isVPS = true
        stk.clear()
        
        for(ch in str) {
            if (ch == '(') {
                // 스택에 여는 괄호 추가
                stk.push(ch)
            } else if (ch == ')') {
                // 스택이 비었거나 여는 괄호가 아니라면 VPS가 아님
                if(stk.isEmpty() || stk.peek() != '(') {
                    isVPS = false
                    break
                }

                // 스택이 비어있지 않고, 여는 괄호 일 경우 스택에서 제거
                stk.pop()
            }
        }

        // 전부 순회 하였는데 스택 비어있지 않으면 VPS가 아님
        if(stk.size != 0) isVPS = false

        if(isVPS) println("YES")
        else println("NO")
    }
}

코드 보기(Python)

from sys import stdin

def main():
    stk = []
    # 테스트 케이스 개수 입력
    N = int(stdin.readline())
    for _ in range(N):
        inp = stdin.readline()
        isVPS = True
        stk.clear()
    
        for ch in inp:
            if ch == '(':
                # 스택에 여는 괄호 추가
                stk.append(ch)
            elif ch == ')':
                # 스택이 비었거나 여는 괄호가 아니라면 VPS가 아님
                if not stk or stk[-1] != '(':
                    isVPS = False
                    break

                # 스택이 비어있지 않고, 여는 괄호 일 경우 스택에서 제거
                stk.pop()

        # 전부 순회 하였는데 스택 비어있지 않으면 VPS가 아님
        if stk:
            isVPS = False

        if isVPS:
            print("YES")
        else:
            print("NO")
            
if __name__ == "__main__":
    main()

코드 보기(Swift)

import Foundation

func main() {
    var stk = Array<Character>()
    
    // 테스트 케이스 갯수 입력
    var N = Int(readLine()!)!
    for i in 0..<N {
        // 괄호 문자열 입력
        var str = readLine()!
        var isVPS = true
        stk.removeAll()
        
        for ch in str {
            if (ch == "(") {
                // 스택에 여는 괄호 추가
                stk.append(ch)
            } else if (ch == ")") {
                // 스택이 비었거나 여는 괄호가 아니라면 VPS가 아님
                if(stk.isEmpty || stk.last != "(") {
                    isVPS = false
                    break
                }

                // 스택이 비어있지 않고, 여는 괄호 일 경우 스택에서 제거
                stk.popLast()
            }
        }

        // 전부 순회 하였는데 스택 비어있지 않으면 VPS가 아님
        if !stk.isEmpty {
            isVPS = false
        }
        
        if isVPS {
            print("YES")
        } else {
            print("NO")
        }
    }
}

main()