글 읽기 - Trie로 풀기전 작성한 코드가 틀린 이유를 도저히 모르겠습니다...

fpekrkfk_h 3년 전 0

제 생각대로 코드를 작성한 후 계속해서 틀리다고 나와 다른 분들 풀이를 참고하여 Trie로 풀어 맞기는 했으나

그전에 제가 작성한 코드가 왜 틀렸다고 나오는지 도저히 이해가 되지 않아 질문을 남깁니다...

트리 형태로 만들어서 풀었고, ArrayList의 contains를 사용하기 위해 sChild라는 리스트에 String값만 넣어놨고,

같은 index에 해당 Node를 담았습니다.

이부분은 출력할때 정렬해서 출력하여 문제가 없을 것 같은데 어떤 부분에서 문제가 있을까요 ㅠㅠㅠ

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

// BOJ 14725 개미굴
public class Main {
    public static StringBuilder sb = new StringBuilder();
    public static String af = "--";

    public static void dfs(Node root, int count){
        int cc = count;
        if(!root.data.equals("")) {
            while(cc-- > 0){
                sb.append(af);
            }
            sb.append(root.data).append("\n");
        }

        if(root.child.size() == 0) {
            return;
        }

        Collections.sort(root.child, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                return o1.data.compareTo(o2.data);
            }
        });
        for(Node e : root.child){
            dfs(e, count+1);
        }
    }

    public static void setNodes(Node root, String tmp) {
        String[] data = tmp.split(" ");
        int len = data.length;

        setTree(root, data, 0, 0, len);
    }

    public static void setTree(Node root, String[] data, int i, int count, int len) {
        if (count == len)
            return;

        if (!root.sChild.contains(data[i])) {
            root.sChild.add(data[i]);
            root.child.add(new Node(data[i]));
        }
        root = root.child.get(root.sChild.indexOf(data[i]));
        setTree(root, data, i + 1, count + 1, len);
    }

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

        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        Node root = new Node("");
        String[] tmp = new String[T];
        for (int i = 0; i < T; ++i) {
            tmp[i] = br.readLine();
            tmp[i] = tmp[i].substring(2, tmp[i].length());
        }
        for (int i = 0; i < T; ++i){
            setNodes(root, tmp[i]);
        }
        dfs(root, -1);
        System.out.print(sb);
        br.close();
    }

    public static class Node {
        String data;
        ArrayList<Node> child = null;
        ArrayList<String> sChild = null;

        public Node(String data) {
            this.data = data;
            this.child = new ArrayList<>();
            this.sChild = new ArrayList<>();
        }
    }
}

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

문제

문제

출처

ICPC

Trie로 풀기전 작성한 코드가 틀린 이유를 도저히 모르겠습니다...

fpekrkfk_h 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말