글 읽기 - 런타임 에러 인 이유...ㅠㅠ

nhs0912 6년 전 0

이거 왜 런타임 에러가 뜰까요??

혹시 입력을 할 때 아래와 같이 노드의 갯수대로 되어야하는데

A . .

-----------------------------------------

A B C

노드의 갯수는 1개인데 입력된 것은 3개인 이런 입력 예제가 있어서 그런걸까요??

이것도 다 에러를 잡아줘야하나요??

import java.io.*;
import java.util.StringTokenizer;

/**
 * 문제 이름 : 트리 순회
 * 문제 번호 : 1991
 * 문제 사이트 : https://www.acmicpc.net/problem/1991
 */
class Main {

    char[] Tree = new char[100];

    void inOrder(int root) {
        if (Tree[root] != '.'&& Tree[root]!='\u0000') {
            inOrder(root * 2);
            System.out.print(Tree[root]);
            inOrder((root * 2) + 1);
        }
    }

    void preOrder(int root) {
        if (Tree[root] != '.' && Tree[root]!='\u0000') {
            System.out.print(Tree[root]);
            preOrder(root * 2);
            preOrder((root * 2) + 1);
        }

    }

    void postOrder(int root) {
        if (Tree[root] != '.'&& Tree[root]!='\u0000') {
            postOrder(root * 2);
            postOrder((root * 2) + 1);
            System.out.print(Tree[root]);
        }
    }


    void Solve() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine().trim());
        Tree[1] = 'A';
        int index = 0;
        while (N-- > 0) {//N만큼 입력 받기
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            char data = st.nextToken().charAt(0);
            for (int i = 1; i < Tree.length; i++) {
                if (Tree[i] == data) {
                    index = i;//parent
                    break;
                }
            }
            Tree[index * 2] = st.nextToken().charAt(0); //left
            Tree[(index * 2) + 1] = st.nextToken().charAt(0); //right

        }
        preOrder(1);
        System.out.println();
        inOrder(1);
        System.out.println();
        postOrder(1);
    }

    public static void main(String[] args) throws IOException {
        new Main().Solve();
    }
}

bupjae 6년 전 1

다음과 같은 입력 데이터가 들어왔을 때 Tree 배열의 범위를 넘어서는 걸로 보입니다.

26
A B .
B C .
C D .
D E .
E F .
F G .
G H .
H I .
I J .
J K .
K L .
L M .
M N .
N O .
O P .
P Q .
Q R .
R S .
S T .
T U .
U V .
V W .
W X .
X Y .
Y Z .
Z . .

nhs0912 6년 전 0

근데 이거 왜 트리 크기가 넘어가는걸까요?

노드의 갯수가 26개까지인데

맨 마지막 26번째 노드의 자식이라고 해봤자 배열 인덱스 52번째랑 53번째인데요.

그럼 크기를 root 인덱스가 1이라고 한다면 크기를 54로 지정하면 이 범위를 벗어나지 않지 않나요???

bupjae 6년 전 1

실제로 돌려보면

A는 [1] 에 저장되고

B는 [2], C는 [4], D는 [8], E는 [16], F는 [32], G는 [64]

H는 [128]에 저장하려다가 배열 범위를 벗어납니다.

nhs0912 6년 전 0

어제 생각해봤는데 최악의 경우 트리의 높이가 26인 경우도 있더라고요..그래서 2^26-1개의 노드가 생성되어야하더라고요..

그래서 그 크기만큼 배열 크기를 지정하니깐 이상없이 잘 되네요!

답변 정말 감사합니다! 덕분에 큰 도움 되었습니다^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

런타임 에러 인 이유...ㅠㅠ

nhs0912 6년 전 0

bupjae 6년 전 1

nhs0912 6년 전 0

bupjae 6년 전 1

nhs0912 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말