Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

18. 스택

스택을 구현하고 사용해 봅시다.

Java / Python

3. 괄호

9012번

주어진 문자열이 올바른 괄호열인지 판단하는 문제

이번 문제는 올바른 괄호열인지 확인하는 문제입니다.
알맞은 괄호 수식의 원리는 여는 괄호 '(' 가 있으면 반드시 이에 대응하는 닫는 괄호 ')' 가 있어야한다는 것입니다. 스택을 활용할 때, 이 원리를 이용해서 여는 괄호가 있을 때는 스택에 쌓고 닫는 괄호가 있으면 여는 괄호를 하나 지우면(pop)됩니다.
경우는 다음과 같습니다.

• 완전한 수식인 경우 최종적으로 스택에 아무 것도 없어야 합니다.
• 모든 괄호를 검사한 후 스택에 괄호가 남는 경우는 여는 괄호가 많은 경우라는 의미입니다.
• 닫는 괄호가 더 많을 경우에는 이미 비어있는 스택을 더 pop해야해, error가 날 수 있습니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			sb.append(solve(br.readLine())).append('\n');
		}
		
		System.out.println(sb);
	}
 
	public static String solve(String s) {
 
		Stack<Character> stack = new Stack<>();
 
		for (int i = 0; i < s.length(); i++) {
 
			char c = s.charAt(i); 
			
			if (c == '(') {	// 여는 괄호일 경우 스택에 넣는다.
				stack.push(c);
			}else if (stack.empty()) {	// 스택이 비어있는 경우
				return "NO";
			}else {	// 닫는 괄호 (스택 비어있지 않은 경우)
				stack.pop();
			}
		}
 
		if (stack.empty()) {
			return "YES";	// 모두 완료 후 스택이 비어있으면 알맞는 수식
		}else {
			return "NO";
		}
	}
}

• Python

import sys
T = int(sys.stdin.readline()) 
for _ in range(T): 
    stack = [] 
    s = sys.stdin.readline() 
    check = 0 
    for c in s: 
        if c =='(': 
            stack.append(c) 
        elif c ==')': 
            if len(stack) ==0: 
                print('NO') 
                check = 1 
                break 
            else: 
                stack.pop(-1) 
    if len(stack) != 0 and check == 0: 
        print('NO') 
    elif len(stack) ==0 and check ==0: 
        print('YES')