백준 괄호 문제 풀이

문제링크

사용한 자료구조: 스택

최근에 들어온 데이터부터 처리를 해주어야 하기 때문에 스택을 선택하였다.

찾아낸 규칙

"("가 들어오면 일단 스택에 넣는다.
그리고 ")"가 들어왔을때, 스택에 "("가 있으면 팝하고, 스택이 비어있으면 유효한 괄호 쌍이 아니다.
그리고 최종적으로 쌍이 맞다면 스택은 비어있을 것이고 그게 아니라면 스택은 비어있지 않을 것이다.

코드 및 코드 설명

import java.util.Scanner;
import java.util.Stack;

public class Vps {
    public static boolean solution(String s){
        Stack<Character> stack =  new Stack<>();
        char[] cArr = s.toCharArray(); // 문자열로 들어온 괄호를 char로 분리한다.
        boolean isVps = true; // 유효한 괄호쌍인지 판단하는 변수
        for(int i = 0; i<s.length(); i++){ // 모든 문자를 순회하며
            if(cArr[i] == '('){ // 열린괄호면 스택에 넣는다.
                stack.push(cArr[i]);
            } else { // 닫힌괄호일때,
                if(stack.isEmpty() || stack.peek() !='('){ // 스택이 비어있거나, 열린괄호가 top에 없다면
                    isVps =false; // 유효한 괄호쌍이 아니다.
                    break; // 유효하지 않으므로 순회를 멈춘다.
                } else{
                    stack.pop(); // 스택에 열린괄호가 있다면 쌍이 맞으므로 pop한다.
                }
            }
        }
        if(stack.isEmpty() && isVps){ // 만약 스택이 비어있고 유효한 괄호쌍이라면 true
            return true;
        } else{
            return false;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            String s= sc.next();
            if (solution(s)) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}