[백준_Stack]9012번_괄호
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(); |
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 |