[백준-9012] 괄호

[백준-9012] 괄호

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 

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

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	16300	6289	4832	38.886%

---

코드작성은 30분정도, 기타 수정까지 2시간 정도 걸린듯하다.

난이도는 하.

JAVA 1 - Stack 사용. 정석

public class Main {
    public static void main(String[] args) {
        java.util.Scanner scan = new java.util.Scanner(System.in);
        String num = scan.nextLine();
        while(scan.hasNext()){
            String line = scan.nextLine();
            ArrayStack stack = new ArrayStack(line.length());
            System.out.println(stack.checkVPS(line));
        }


    }

    public static class ArrayStack {
        private int top;
        private int maxSize;
        private String[] array;

        public ArrayStack(int maxSize) {
            this.top = -1;
            this.maxSize = maxSize;
            this.array = new String[maxSize];
        }

        // empty check
        private boolean empty(){
            return (top == -1);
        }

        // full check
        private boolean full(){
            return (top == maxSize-1);
        }

        // push
        public void push(String item){
            if(full()) System.out.println("Stack Full :"+(top+1)+">=" + maxSize);
            array[++top] = item;
        }


        // pop
        public String pop()throws Exception{
            if(empty()) throw new Exception("Stack Empty : top = "+top);
            String item = array[top];
            top--;

            return item;
        }

        public String checkVPS(String line){
            for (int i = 0; i < line.length(); i++) {
                try {
                    String s = String.valueOf(line.charAt(i));
                    if ("(".equals(s)) {
                        push(s);
                    } else if (")".equals(s)) {
                        pop();
                    }
                }catch (Exception e){
                    return "NO";
                }
            }

            if(top == -1){
                return "YES";
            }else{
                return "NO";
            }
        }
    }
}

결과

메모리 : 9500 KB / 시간 : 112 ms

흠 좀더 줄여봐야지

java 2 >> stack 안쓰고 함수로 뺌

public class Main {
    public static void main(String[] args) {
        int i=0;
        java.util.Scanner scan = new java.util.Scanner(System.in);
        String num = scan.nextLine();
        while(scan.hasNext()){
            String line = scan.nextLine();
            System.out.println(checkVPS(line));
        }


    }
    public static String checkVPS(String line){
        int num=0;
        for (int i = 0; i < line.length(); i++) {
            String s = String.valueOf(line.charAt(i));
            if ("(".equals(s)) {
                num++;
            } else if (")".equals(s)) {
                num--;
                if(num <0 )
                    return "NO";
            }
        }
        if(num == 0){
            return "YES";
        }else{
            return "NO";
        }
    }
}

결과

메모리 : 9508 KB / 시간 : 112 ms

흠...70초대는 어케 만든거지...

java 2 >> hasNext 안쓰고 제시된 개수 사용

java.util.Scanner scan = new java.util.Scanner(System.in);
int num = Integer.parseInt(scan.nextLine());
for (int i = 0; i < num; i++) {
    String line = scan.nextLine();
    System.out.println(checkVPS(line));
}

메모리 : 9504 KB / 시간 : 108 ms

쪼오금 줄긴 줄엇다

java 3 >> BufferedReader 사용

try {
    java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    int num = Integer.parseInt(br.readLine());
    for (int i = 0; i < num; i++) {
        String line = br.readLine();
        System.out.println(checkVPS(line));
    }
}catch (Exception e){
    e.printStackTrace();
}

메모리 : 9136 KB / 시간 : 76 ms

시간이 반으로 줄엇다

java 3 >> StringBuilder 사용

StringBuilder sb = new StringBuilder();
try {
    java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
    int num = Integer.parseInt(br.readLine());
    for (int i = 0; i < num; i++) {
        String line = br.readLine();
        sb.append(checkVPS(line));
    }
}catch (Exception e){
    e.printStackTrace();
}

메모리 : 9296 KB / 시간 : 72 ms

?? 메모리 늘어남 

아 백준 채점 너무 느리다..

java 4 >> 추가 수정

public class Main {

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

        StringBuilder sb = new StringBuilder();

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

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

        for (;count>0;count--) {

            String line = br.readLine();

            int num=0;

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

                String s = String.valueOf(line.charAt(i));

                if ("(".equals(s)) {

                    num++;

                } else {

                    num--;

                    if(num <0 ){

                        sb.append("NO\n"); break;

                    }

                    

                }

            }

            if(num == 0){

                    sb.append("YES\n");

            }else if (num > 0){        

                    sb.append("NO\n");

            }

            

        }

        

        System.out.println(sb.toString());

    }

}

메모리 : 9136 KB / 시간 : 72 ms

흠 여기까지인거로...ㅠ