[백준] 9012: 괄호

문제

문제 풀이

문제는 다음과 같은 경우의 수를 가질 수 있다.

• 여는 괄호('(')가 추가되는 경우 리스트에 추가한다.
• 닫는 괄호(')')가 추가되는 경우
  - 리스트가 비어있을 경우, VPS가 아니므로 NO를 출력한다.
  • 리스트가 비어있지 않은 경우,
  • 이전 인덱스에 해당하는 원소가 여는 괄호('(')일 경우, VPS이므로 이전 인덱스 해당하는 원소를 pop한다.
  • 이전 인덱스 해당하는 원소가 닫는 괄호(')')일 경우, VPS가 아니므로 해당 인덱스에 원소를 추가한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class ANS9012 {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());


        for(int i = 0 ; i < T ; i++){
            List<String> list = new ArrayList<String>();
            String s= br.readLine();
            int index = 0;
            for(int j = 0 ; j < s.length() ; j++){
                if(list.isEmpty()){
                    list.add(String.valueOf(s.charAt(j)));
                    index++;
                }else{
                    if((s.charAt(j) == ')') && (list.get(index-1).equals(String.valueOf('(')))){
                        list.remove(index -1);
                        index--;
                    }else{
                        list.add(String.valueOf(s.charAt(j)));
                        index++;
                    }
                }

            }
            if(list.isEmpty()){
                System.out.println("YES");
            }else{
                System.out.println("NO");
            }
        }

    }
}

알고보니 자바에서 스택을 제공하고 있어, 후에 다음과 같이 코드를 작성하였다.

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

public class SOL9012 {

    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);
            }

            //스택이 비어 있는 경우, 즉 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
            else if(stack.empty()){
                return "NO";
            }

            //닫는 괄호 일 경우, 그 전 에 있는 여는 괄호를 pop한다.
            else{
                stack.pop();
            }
        }

        if(stack.empty()){
            return "YES";
        }
        else{
            return "NO";
        }
    }
}