* 핵심 개념
Stack을 사용해 풀 수 있는 문제다.
다양한 방법이 있지만 필자는 입력받은 문자를 Stack에 넣어가며 값을 비교했다.
Stack에 ()와 [] 짝이 안맞다면 강제로 종료하면 되고,
아니면 ()인 경우 2를, []인 경우 3을 스텍에 넣어준다.
만약, Stack에 [,2,3 이 들어있다면 2+3을 하고 현재 문자가 ] 이라면 *3을 하면 된다.
마지막에 Stack을 돌면서 숫자를 전부 더해주면 된다.
예외 처리는 맨 처음부터 ')'나 ']'가 들어왔을때 처리해야 한다.
* 문제
문제
4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.
- 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.
- 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.
- X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.
예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.
- ‘()’ 인 괄호열의 값은 2이다.
- ‘[]’ 인 괄호열의 값은 3이다.
- ‘(X)’ 의 괄호값은 2×값(X) 으로 계산된다.
- ‘[X]’ 의 괄호값은 3×값(X) 으로 계산된다.
- 올바른 괄호열 X와 Y가 결합된 XY의 괄호값은 값(XY)= 값(X)+값(Y) 로 계산된다.
예를 들어 ‘(()[[]])([])’ 의 괄호값을 구해보자. ‘()[[]]’ 의 괄호값이 2 + 3×3=11 이므로 ‘(()[[ ]])’의 괄호값은 2×11=22 이다. 그리고 ‘([])’의 값은 2×3=6 이므로 전체 괄호열의 값은 22 + 6 = 28 이다.
여러분이 풀어야 할 문제는 주어진 괄호열을 읽고 그 괄호값을 앞에서 정의한대로 계산하여 출력하는 것이다.
입력
첫째 줄에 괄호열을 나타내는 문자열(스트링)이 주어진다. 단 그 길이는 1 이상, 30 이하이다.
출력
첫째 줄에 그 괄호열의 값을 나타내는 정수를 출력한다. 만일 입력이 올바르지 못한 괄호열이면 반드시 0을 출력해야 한다.
* 소스 코드
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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 | import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readLine(); Stack<String> stack = new Stack<>(); int sum = 0; String past; for (int i = 0; i < input.length(); i++) { char ch = input.charAt(i); switch (ch) { case '(': case '[': stack.push(Character.toString(ch)); break; case ')': check(stack.size()); past = stack.pop(); if (past.equals("(")) { stack.push(String.valueOf(2)); } else if (past.equals("[")) { //예외 처리 System.out.println("0"); System.exit(0); } else { //stack에 숫자가 잇다면 int add = Integer.parseInt(past); //숫자라면 while (check(stack.size()) && !stack.peek().equals("(")) { String check = stack.pop(); if (!check.equals("[") && !check.equals("(")) { add += Integer.parseInt(check); } } stack.pop(); stack.push(String.valueOf(add * 2)); } break; case ']': check(stack.size()); past = stack.pop(); if (past.equals("[")) { stack.push(String.valueOf(3)); } else if (past.equals("(")) { System.out.println("0"); System.exit(0); } else { //stack에 숫자가 잇다면 int add = Integer.parseInt(past); while (check(stack.size()) && !stack.peek().equals("[")) { String check = stack.pop(); if (!check.equals("[") && !check.equals("(")) { add += Integer.parseInt(check); } } stack.pop(); stack.push(String.valueOf(add * 3)); } break; } } while (!stack.isEmpty()) { try { sum += Integer.parseInt(stack.pop()); } catch (Exception e) { sum = 0; break; } } System.out.println(sum); } public static boolean check(int size) { if (size != 0) return true; else { System.out.println("0"); System.exit(0); return false; } } } | cs |
'∙Algorithm' 카테고리의 다른 글
| [Algorithm] 백준/11657 :: 타임머신 (0) | 2019.04.30 |
|---|---|
| [Algorithm] 백준/1026 :: 보물 (0) | 2019.04.30 |
| [Algorithm] 백준/2493 :: 탑 (0) | 2019.04.27 |
| [Algorithm] 백준/1655 :: 가운데를 말해요 (0) | 2019.04.21 |
