[백준/알고리즘/python/java] 9012번 - 괄호

이미지를 누르면 문제링크를 보실 수 있습니다.

이미지를 누르면 문제링크를 보실 수 있습니다.

[9012번 - 괄호]

괄호 문제는 스택 문제중에서도 흔한 유형에 속한다.

여는 괄호와 닫힌 괄호가 쌍을 이루고, 짝이 맞는다면 올바른 괄호 문자열 (Valid PS, VPS) 인 것이다.

 

(코드는 아래와 같다.-파이썬,python)

import sys
input = sys.stdin.readline
testcase = int(input())
for i in range(testcase):
    bracket = []
    stack = []
    command = input()
    bracket.append(command)
    for j in command:
        if j == "(":
            stack.append(j)
        elif j == ")":
            if(len(stack) == 0):
                break
            else:
                stack.pop(-1)
    if(j == command[-1] and len(stack) == 0):
        print("YES")
    else:
        print("NO")

bracket 이라는 리스트를 굳이 만들지 않고 command를 바로 탐색해도 된다.

로직은 입력값으로 괄호들을 입력받는다.

반복문을 통해서 괄호를 탐색하는데,

해당 탐색 괄호가 "(" 여는 괄호라면, stack 에 넣고

해당 탐색 괄호가 ")" 닫는 괄호라면, stack의 가장 끝 원소를 빼낸다.

VPS 에 해당하는 입력이라면, 끝까지 입력된 괄호들을 탐색할 것이고,

stack 의 길이는 0 일 것이다. (여는 괄호가 닫는 괄호와 쌍을 이루니까 쌓였던 여는 괄호는 다 없어졌을 것이다.)

 

이 때 주의할 점은, 

")" 닫는 괄호가 처음부터 입력 될 수 있으니, stack의 길이가 0인 상태에서 탐색 괄호가 ")" 라면 바로 "NO"를

입력하도록 반복문을 빠져나오게 해야 한다.

 

(아래는 이전에 풀었던 자바 코드이다 - java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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.setLength(0);
			boolean isVPS = true;
			String st = (br.readLine());
			Stack<String> stack = new Stack<>();
			for(int j=0;j<st.length();j++) {
				if(st.charAt(j)=='('){
					stack.push(String.valueOf(st.charAt(j)));
				}
				else if(st.charAt(j)==')') {
					if(!stack.isEmpty() && stack.peek().equals("(")) {
						stack.pop();
					}
					else {
						isVPS = false;
						break;
					}
				}
			}
			if(!stack.isEmpty()) {
				isVPS = false;
			}
			if(isVPS) {  // isVPS 가 true 이면
				sb.append("YES");
				System.out.println(sb.toString());
			}
			else {
				sb.append("NO");
				System.out.println(sb.toString());
			}
			}
		}
	}