[SWEA] 1218 괄호 짝짓기

출처: [SWEA] 1218 괄호 짝짓기

 Input 
182
(({<(({{[[[[<<[[(<[[{([{{{[<[[[{<<(<[[{}[]{}{}[]]]><><...
298
{(({[({([{(<[([(([<({[{{[[({{[({([<{(<[[((<{{[([{<<[{(<({[<(...

 Output 

#1 1
#2 0

 

4 종류의 괄호문자들 '()', '[]', '{}', '<>' 로 이루어진 문자열이 주어진다.

이 문자열에 사용된 괄호들의 짝이 모두 맞는지 판별하는 프로그램을 작성한다.

[유효한 Case]

[유효하지 않은 Case]

총 10개의 Test Case가 주어집니다. (지면 관계상 예제 1개만 게재)

▶ 괄호 유효성 여부를 『`1』 또는 『0』으로 출력 (1: 유효 / 0: 유효하지 않음)

 

 

스택(Stack) 이용

Last In First Out (LIFO) 구조로

① 여는 괄호 '{' , '[' , '<', '(' 기호가 나오면 Stack Push

② 닫는 괄호 '}', ']', '>', ')' 기호가 나올 경우 stack.peek()으로 

    stack에 쌓여있는 마지막 원소(top) 탐색하여 유효성 여부 판단

    괄호 종류에 맞는 쌍이 아닌 경우 잘못된 경우로 종료해도 되지만, 닫는 괄호를 Stack Push

③ Stack이 비워져 있는지 확인하여 유효성 판단.

 

▶  [스택] Stack 이란? 

[스택] Stack 이란?

---

C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;
 
int main() {
    int testCase = 10;
    
    int len;
    string str;
    bool isValid;
    for (int tc = 1; tc <= testCase; tc++) {
        cin >> len >> str;
        stack<char> st;
        isValid = true;
        for (int i = 0; i < len; i++) {
            // 열린 괄호인 경우 push
            if(str[i] == '(' || str[i] == '[' || str[i] == '{' || str[i] == '<'){
                st.push(str[i]);
                continue;
            }
 
            // 닫힌 괄호인 경우 스택이 비워져 있는지 확인
            if (st.empty()) {
                isValid = false;
                break;
            }
            // 괄호쌍 검토
            if (str[i] == ')' && st.top() != '(' ) isValid = false;
            else if (str[i] == ']' && st.top() != '[') isValid = false;
            else if (str[i] == '}' && st.top() != '{') isValid = false;
            else if (str[i] == '>' && st.top() != '<') isValid = false;    
 
            // 유효하지 않는 것이 판단된 경우
            if (!isValid) break; 
 
            // 현재까지는 괄호쌍이 맞는 경우
            st.pop();
        }
 
        // 모든 괄호를 처리했는데 stack에 남아 있는지 확인
        if (st.size() > 0) isValid = false;
        
        cout << "#" << tc << " ";
        if (isValid) cout << "1\n";
        else cout << "0\n";
    }
}

 

Java

import java.io.*;
import java.util.*;
 
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        for (int tc = 1; tc <= 10; tc++) {
            int len = Integer.parseInt(br.readLine());
            String str = br.readLine();
 
            int answer = 0;
            Stack<Character> stack = new Stack();
            for (int i = 0; i < len; i++) {
                char c = str.charAt(i);
                // 닫힌 괄호 종류에 맞는 쌍 유효성 여부를 확인하여 제거
                // stack이 비어있지 않은 상태에서 peek() 가능
                if (c == ')' && !stack.isEmpty() && stack.peek() == '(')
                    stack.pop();
                else if (c == ']' && !stack.isEmpty() && stack.peek() == '[')
                    stack.pop();
                else if (c == '}' && !stack.isEmpty() && stack.peek() == '{')
                    stack.pop();
                else if (c == '>' && !stack.isEmpty() && stack.peek() == '<')
                    stack.pop();
                else // 여는 괄호이거나 닫는 괄호 쌍이 맞지 않은 경우 닫는 괄호도 stack push
                    stack.push(c);
            }
 
            if (stack.isEmpty()) {
                // 스택이 모두 비워진 경우
                answer = 1;
            } 
            else {
                answer = 0;
            }
 
            // 정답 출력
            System.out.println("#" + tc + " " + answer);
        }
    }
}