[백준알고리즘] 자료구조 - 9012번 VPS 문제

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

9012번: 괄호

딱봐도 스택 써서 풀라고 만든 문제처럼 생겼지만

나는 일단 스택을 직접 구현해서 풀진 않았다

문자열을 훑다가 (가 나오면 isLeft라는 변수값을 증가시키고, 반대로 )가 나온다면 감소시키는 방식으로 나름 간단하게 풀어보려 했다

문자열 탐색이 다 끝나고 났을때 IsLeft값이 0이 되었다는건 괄호가 다 맞아떨어져 vps라는 의미이므로 yes를 출력하면 되고

값이 0보다 크다면 스택에 남아있는 괄호값이 남아있다는 것과 마찬가지이므로 vps가 아님, no를 출력한다

이때 주의할점이 For문 반복을 하면서 isLeft값이 음수값이 될 경우인데,

이건 '('가 남아있지도 않은 상태에서 ')'문자가 들어왔다는 의미이므로 이미 vps가 아니게 된다

만약 여기서 반복문 탈출을 하지 않고 끝까지 돌게 된다면 vps가 아님에도 불구하고 isLeft값이 0이 될 우려가 있다

(예를들어 "(()))("의 경우를 생각해보면..)

 

그렇게 해서 통과한 코드는 맞지만 그래도 자료구조 복습 겸 선정한 문제인데 스택을 써서 풀긴 해야할것 같다

내일 스택 사용한 코드 또한 다시 풀이해서 올리도록 하겠다!

 

<풀이코드>

package week1;

import java.io.*;

public class Parenthesis {  //괄호 문자열 문제, 백준 9012번
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());    //입력 문자열 개수

        String str = "";
        char chr;
        String result;
        int isLeft = 0; //닫히지 않은 괄호 남아있다면 마지막에 양수가 남아있을것이고 vps라면 마지막에 0의 값이 될것임

        for (int i = 0; i < N; i++) {
            str = br.readLine();
            isLeft = 0;
            for (int j = 0; j < str.length(); j++) {
                if (isLeft < 0) {
                    break;  //음수가 되었다는건 더 볼필요도 없이 vps가 아닐것
                    //만약 여기서 이렇게 확인을 안한다면 잘못된 결과 나올수도 있을것임 (예를들어 (()))(도 vps라고 하면 안되니까)
                }
                chr = str.charAt(j);
                if (chr == '(') {
                    isLeft++;
                } else if (chr == ')') {
                    isLeft--;
                }
            }

            if (isLeft == 0) {
                bw.write("YES");
                bw.newLine();
            }else{
                bw.write("NO");
                bw.newLine();
            }
        }
        bw.flush();
        bw.close();





    }
}