📜 문제

https://www.acmicpc.net/problem/9012

문제 분석

• 핵심 포인트
  괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다.
  입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단 → 간단히 말해서, 짝이 맞아야 한다.

🎯 풀이

알고리즘 알고 풀기

• 알아야 하는 개념은 스택이다.
  스택이란 LIFO(후입선출)방식의 자료구조이다.
  스택은 한쪽 끝에서만 값을 넣고 꺼낼 수 있다.

 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;


public class jun_9012 {
    public static void main(String[] args) throws IOException {

        // 입력을 받기 위한 설정
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(bf.readLine());
		
        // T만큼 반복
        while (T-- > 0) {
            boolean isVPS = true; // 괄호의 짝이 맞는지 판별
            String input = bf.readLine(); // 괄호 입력값 저장
            Stack<Character> stack = new Stack<Character>(); // 스택 생성
            char c; // 입력 문자열을 하나씩 저장할 변수

            // 여는 괄호만 스택에 넣는다.
            for(int i = 0 ; i < input.length() ; i++){
                c = input.charAt(i); // 입력 문자열을 하나씩 저장

                if (c == '('){
                    stack.push(c);
                }

                else if (c == ')'){ // 닫는 괄호인 경우 스택이 비었는지 판별한다.
                    if(!stack.isEmpty()){ // 스택이 비지 않은 경우(스택에 여는 괄호가 있다.)
                        stack.pop(); //  pop
                      } else {  // 스택이 빈 경우(스택에 여는 괄호가 없다.)
                        isVPS = false; // 닫힌 괄호가 나오면 false
                        break;
                    }
                }
            }

            if(!stack.isEmpty()) {isVPS = false;} // 괄호의 짝이 맞지 않았을 경우 false

            if(isVPS) {
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        } // while 반복문 종료
    }
}

시간복잡도

이중 for문을 사용했기 때문에 O(n2)

공간복잡도

Ref