(2504) 괄호의 값 (Java)


시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초128 MB51757136021023429.698%

문제

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

(()[[]])([])

예제 출력 1

28

예제 입력 2

[][]((])

예제 출력 2

0

출처

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 초등부 4번

Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2008 > 중등부 2번

데이터를 추가한 사람: 906bc, djm03178, eatgugbab, ikissedagirl, leedongbin, sang7, sankim90, sayfour, whiteque
잘못된 데이터를 찾은 사람: djm03178

알고리즘 분류

구현
자료 구조
스택

Solution

1 런타임 에러

import java.io.*;
import java.util.Stack;

public class Main {
    public static String str;
    public static int answer;
    public static Stack<Character> stk;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        str = br.readLine();

        bw.write(String.valueOf(calValue(str)));
        bw.flush();
        bw.close();
        br.close();
    }

    public static int calValue(String str) {
        stk = new Stack<Character>();
        char ch;
        int tmp = 1;
        answer = 0;

        for(int i = 0; i < str.length(); i++) {
            ch = str.charAt(i);

            if(ch == '(') {
                stk.push(ch);
                tmp *= 2;
            } else if(ch == '[') {
                stk.push(ch);
                tmp *= 3;
            } else if(ch == ')') {
                if(stk.peek() != '(' || stk.isEmpty()) {
                    return 0;
                } else if (str.charAt(i-1) == '(') {
                    answer += tmp;
                }
                stk.pop();
                tmp /= 2;
            } else if(ch == ']') {
                if(stk.peek() != '[' || stk.isEmpty()) {
                    return 0;
                } else if(str.charAt(i-1) == '[') {
                    answer += tmp;
                }
                stk.pop();
                tmp /= 3;
            }
        }

        return answer;
    }
}

2

import java.io.*;
import java.util.Stack;

public class Main {
    public static String str;
    public static int answer;
    public static Stack<Character> stk;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        str = br.readLine();

        bw.write(String.valueOf(calValue(str)));
        bw.flush();
        bw.close();
        br.close();
    }

    public static int calValue(String str) {
        stk = new Stack<Character>();
        char ch;
        int tmp = 1;
        answer = 0;

        for(int i = 0; i < str.length(); i++) {
            ch = str.charAt(i);

            if(ch == '(') {
                stk.push(ch);
                tmp *= 2;
            } else if(ch == '[') {
                stk.push(ch);
                tmp *= 3;
            } else if(ch == ')') {
                if(stk.isEmpty() || stk.peek() != '(') {
                    return 0;
                } else if (str.charAt(i-1) == '(') {
                    answer += tmp;
                }
                stk.pop();
                tmp /= 2;
            } else if(ch == ']') {
                if(stk.isEmpty() || stk.peek() != '[') {
                    return 0;
                } else if(str.charAt(i-1) == '[') {
                    answer += tmp;
                }
                stk.pop();
                tmp /= 3;
            }
        }

        if(!stk.isEmpty()) {
            return 0;
        }

        return answer;
    }
}

Feedback

stk의 peek를 체크하기 전에 비어있는지를 먼저 체크했어야 함. 입력값으로 ] 이 주어질 경우 스택이 비어있는 상태에서 peek를 호출하므로 에러 발생함
그런데도 정답이 아니길래 봤더니, ((() 와 같은 입력의 경우 올바르지 못한 괄호임에도 불구하고 2 2 2 = 6을 출력하고 있었다.
괄호 문자열을 모두 순회한 후에 스택에 원소가 남아있는 경우를 체크해야 했다.

profile
Opportunities are never lost. The other fellow takes those you miss.

0개의 댓글

Powered by GraphCDN, the GraphQL CDN