글 읽기 - (트리의 높이와 너비) 틀린 테스트케이스를 찾지 못하겠습니다...

jduck1024 4년 전 0

트리 생성 후 중위순회를 하여 리스트에 레벨과 열 번호를 저장한 후 레벨이 같은 노드끼리 집합을 이루어 오름차순으로 정렬한 후 같은 레벨인 노드들 사이에서 열 번호를 오름차순으로 정렬한 후 답을 구하는 방식으로 코드를 짰는데 틀린 테스트케이스를 찾지 못하겠습니다... 도와주세요 부탁드립니다...!

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Sort sort = new Sort();
        Circulation c = new Circulation();
        Tree tree = new Tree();
        List<StoredInfo> arr;
        int value;
        int left;
        int right;
        int n = scan.nextInt();

        for (int i = 0; i < n; i++) {
            value = scan.nextInt();
            left = scan.nextInt();
            right = scan.nextInt();
            if (i == 0) {
                tree = new Tree(value);
            }
            tree.put(value, left, right);
        }

        arr = c.inOrder(tree.getRoot(), 1);

        Collections.sort(arr, sort);

        int max = 1;
        int level = 1;
        if(arr.size() > 1){
            int temp = arr.get(1).colNum;
            for(int i = 1 ; i < arr.size() ; i++){
                if(i < arr.size() - 1){
                    if( arr.get(i).level != arr.get(i + 1).level && arr.get(i).colNum - temp + 1 > max){
                        level = arr.get(i).level;
                        max = arr.get(i).colNum - temp + 1;
                        temp = arr.get(i + 1).colNum;
                    }
                }else{
                    if (arr.get(i).level == arr.get(i - 1).level && arr.get(i).colNum - temp + 1 > max) {
                        level = arr.get(i).level;
                        max = arr.get(i).colNum - temp + 1;
                    }
                }
            }
        } // 답 찾는 과정
        System.out.print(level + " " + max);
    }
}

class Circulation {
    private List<StoredInfo> si = new ArrayList<>();
    private int colNum = 1;

    List<StoredInfo> inOrder(Node n, int level) {
        if (n != null) {
            inOrder(n.getLeft(), level + 1);
            colNum = colNum + 1;
            si.add(new StoredInfo(level, colNum));
            inOrder(n.getRight(), level + 1);
        }
        return si;
    } //중위 순회
}

class Node {
    private Node left;
    private Node right;
    private int value;

    Node(int value) {
        this.value = value;
        left = null;
        right = null;
    }

    int getValue() {
        return value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }
}

class Tree {
    private Node root;

    Tree(){
        root = null;
    }

    Tree(int value) {
        root = new Node(value);
    }

    Node getRoot() {
        return root;
    }

    void put(int value, int left, int right) {
        root = put(root, value, left, right);
    }

    Node put(Node n, int value, int left, int right) {
        if (n != null) {
            if (n.getValue() == value) {
                if (left != -1) {
                    n.setLeft(new Node(left));
                }
                if (right != -1) {
                    n.setRight(new Node(right));
                }
            } else {
                put(n.getLeft(), value, left, right);
                put(n.getRight(), value, left, right);
            }
        }
        return n;
    } //트리 생성
}

class StoredInfo {
    int level;
    int colNum;

    StoredInfo(int level, int colNum) {
        this.level = level;
        this.colNum = colNum;
    }
}

class Sort implements Comparator<StoredInfo> {
    public int compare(StoredInfo a, StoredInfo b) {
        if (a.level > b.level) {
            return 1;
        } else if (a.level == b.level) {
            if (a.colNum > b.colNum) {
                return 1;
            }
        }
        return -1;
    }
} // level이 같은 노드끼리 분류하고 오름차순으로 정렬한 후 level이 같은 노드 집합 내에서 열번호를 오름차순으로 정렬

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

문제

문제

출처

ICPC

(트리의 높이와 너비) 틀린 테스트케이스를 찾지 못하겠습니다...

jduck1024 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말