[백준_Stack]9012번_괄호

Posted by 열정보이
2018. 11. 4. 20:43 Algorithms



Stack을 굳이 이용할 필요가 있을까 하는 생각도 들지만, "Stack을 이렇게도 사용할 수 있구나" 하는 생각에 풀어보았다.




백준 9012번 문제로 입력된 괄호가 짝이 맞아 떨어지면 "YES"를 아닐 경우 "NO"를 출력해주면 되는 문제이다.


나 같은 경우는 입력되는 값이 ( 일 경우 스택에 PUSH 하고, 입력되는 값이 ) 일 경우 POP하여 예외 상황들을 체크하는 

방법을 사용했다.


그렇다면 코드를 직접 보도록 하자


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        Stack<Character> stack = new Stack<>();
        StringBuilder build = new StringBuilder();
        
        for (int i = 0; i < testCase; i++) {
            String str = br.readLine();
            
            if(str.length()%2 != 0) build.append("NO\n");
            else {
                boolean flag = true;
                for (int j = 0; j < str.length(); j++) {
                    char temp = str.charAt(j);
                    
                    if(temp == '(') stack.push('(');
                    else if(temp == ')') {
                        if(stack.isEmpty()) {
                            build.append("NO\n");
                            flag = false;
                            break;
                        }else {
                            stack.pop();
                        }
                    }
                }
                if(stack.isEmpty() && flag)    build.append("YES\n");
                else if(!stack.isEmpty()) build.append("NO\n");
                stack.clear();
            }
        }
        System.out.println(build.toString());
    }
}
 
cs

우선 입력된 문자열의 길이가 홀수일 경우 절대 VPS(Valid Parenthesis String) 가 될 수 없다.


그렇기 때문에 문자열의 길이가 짝수일 경우에만 VPS가 될 수 있는지 확인한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
boolean flag = true;
for (int j = 0; j < str.length(); j++) {
    char temp = str.charAt(j);
    if(temp == '(') stack.push('(');
    else if(temp == ')') {
        if(stack.isEmpty()) {
            build.append("NO\n");
            flag = false;
            break;
        }else {
            stack.pop();
        }
    }
}
if(stack.isEmpty() && flag)    build.append("YES\n");
else if(!stack.isEmpty()) build.append("NO\n");
stack.clear();

cs


flag 변수는 Stack 에 값이 없는데도 불구하고, 입력 값이 ) 일경우 체크해주는 변수이다.


flag 변수를 사용하지 않고 if(stack.isEmpty()) 이렇게만 조건을 줄 경우,  


())) 와 같은 문자열에서 NO 와 YES가 모두 찍힐 수 있기 때문이다.


또한 (((( 와 같은 값이 입력되었을 경우를 체크하기 위해 !stack.isEmpty() 즉, 스택에 값이 남아 있다면 VPS가 아니다 라고 체크하였다.


마지막으로 다음 값을 받기 위해 스택을 비워주는것은 필수!



'Algorithms' 카테고리의 다른 글

[백준_Queue]1966번_프린터 큐  (0) 2018.11.18
[백준_Queue]10845번_큐  (0) 2018.11.13
[백준_Stack]1874번_스택 수열  (0) 2018.11.11
[백준_Stack]2504번_괄호의 값  (0) 2018.11.06
[백준_Stack]10828번_스택  (0) 2018.11.03
Trackback: Comment:

티스토리툴바