[백준] 9012번: 괄호

💡문제 분석 요약

입력으로 주어진 괄호 문자열이 VPS(올바른 괄호 문자열)인지 아닌지를 판별하는 문제이다.

• 시간제한: 1초
• 메모리 제한: 128MB

 

💡알고리즘 설계

• 입력받은 괄호 문자열에서 문자 하나씩 검사한다.
  • ‘(’ 이면 스택에 push
  • ‘)’ 이면
    • 스택이 비어있을 경우 ‘)’를 push하고 반복문 중단.
    • 스택이 비어있지 않을 경우 pop.
• 스택이 비어있으면 “YES”, 비어있지 않으면 “NO”를 결과에 추가한다.

 

💡코드

import java.io.*;
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 n = Integer.parseInt(br.readLine());
        while(n-- > 0) {
            String str = br.readLine();
            Stack<Character> stack = new Stack<>();
            for(char c : str.toCharArray()) {
                if(c == '(') stack.push(c);
                else {
                    if(stack.isEmpty()) {
                        stack.push(c); break;
                    }
                    else stack.pop();
                }
            }
            if(stack.isEmpty()) sb.append("YES").append("\\n");
            else sb.append("NO").append("\\n");
        }

        System.out.println(sb);
        br.close();
    }
}

 

💡시간복잡도

괄호 문자열 길이를 N이라고 할 때, 시간복잡도 O(N)이다.

 

💡 느낀점 or 기억할정보

toCharArray() 와 같이 문자열을 하나씩 나누는 방법을 매번 까먹어서 찾아보게 된다. 자주 사용하기 때문에 기억해두는 것이 좋을 것 같다.