알고리즘 단계별로 풀어보기 : BOJ-9012(괄호)

문제(출처)

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 

그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 

한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 

만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 

그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 

예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다. 

입력

입력 데이터는 표준 입력을 사용한다. 

입력은 T개의 테스트 데이터로 주어진다. 

입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 

각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 

하나의 괄호 문자열의 길이는 2 이상 50 이하이다. 

출력

출력은 표준 출력을 사용한다. 

만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다. 

예제 입력

6

(())())

(((()())()

(()())((()))

((()()(()))(((())))()

()()()()(()()())()

(()((())()(

예제 출력

NO

NO

YES

NO

YES

NO

내 풀이

package date_20190126;

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.Stack;

public class BOJ_9012 {

    // 괄호가 VPS인지 아닌지 확인하는 문제

    

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        

        int num = Integer.parseInt(br.readLine());

        

        Stack<String> s = new Stack<>();

        

        String str = "";

        int o = 0;

        int c = 0;

        String check ="";

        for(int i = 0 ; i < num; i++) {

            str = br.readLine();

            for(int j = str.length()-1 ; j >= 0 ; j--) {

                s.push(String.valueOf(str.charAt(j)));

            }

            

            

            while(!s.isEmpty()) {

                check = s.pop();

                if(check.equals("(")) {

                    o++;

                }else if(check.equals(")")){

                    c++;

                }else {

                    System.out.println("에러");

                }

                

                if(o < c) {

                    s.clear();

//                  스택에 남아 있는 데이터를 삭제한다.

                    break;

                }

            }

            if(o == c) {

                bw.write("YES");

            }else {

                bw.write("NO");

            }

            bw.newLine();

            o = 0;

            c = 0;

        }

        

        bw.close();

    }

}

내 풀이 해석

입력 받은 값을 순서대로 꺼내어 '('의 개수와 ')'의 개수를 비교합니다.

')' 개수가 많으면 카운팅을 종료하고 "NO"를 버퍼에 저장하고 다음 입력을 받습니다.

'('와 ')' 개수가 같다면 "YES"를 버퍼에 저장합니다.

break문이 동작 할 때는 스택에 남아있는 데이터를 모두 제거합니다.

입력 받은 괄호를 스택에 입력 끝 부분부터 저장합니다. 이부분에서 큐를 사용하는게 더 낫지 않을까 했습니다.

아쉬운 점

스택의 특성으로 풀기 보다는 카운팅으로 풀었다.

학습/검색

boolean check = true;

        for(int i = 0; i < str.length(); i++) {

            if(str.charAt(i) == '(') {

                s.push(String.valueOf(str.charAt(i)));

                result.push("2");

            }else {

                if(!s.isEmpty()) {

                    s.pop();

                    lvl--;

                }else {

                    check = false;

                    break;

                }

            }

        }