문제

아이디어

루트 노드부터 시작해 내려가면서 노드를 채워준다.
이 때, 부모 노드를 통해 자식 노드를 탐색하고, 이에 대한 경우의 수는 2가지로 나뉜다.

현재 노드가 이미 부모 노드의 자식으로 등록되어 있는 경우

이 때는 등록된 자식 노드를 가져온 후, 부모 노드에 대입한 후 탐색을 이어간다.

현재 노드가 부모 노드에게 등록되어 있지 않은 경우

이 때는 현재 노드를 부모 노드의 자식으로 등록해 준 후, 현재 노드를 부모 노드에 대입한 후 탐색을 이어간다.

자세한 예시는 문제의 예시를 통해 알아보자.

KIWI BANANA
KIWI APPLE
APPLE APPLE
APPLE BANANA KIWI

KIWI BANANA

루트 노드에 KIWI는 자식으로 등록되어 있지 않다. 루트 노드의 자식 노드로 KIWI를 등록한 후, KIWI를 새로운 부모 노드로 탐색을 이어간다.

KIWI 에 BANANA는 자식으로 등록되어 있지 않다. KIWI 노드의 자식 노드로 BANANA를 등록한 후 다음 줄로 넘어간다.

KIWI APPLE

루트 노드에 KIWI는 자식 노드로 등록되어 있다. KIWI를 새로운 부모 노드로 탐색을 이어간다.

KIWI 에 APPLE은 자식으로 등록되어 있지 않다. KIWI 노드의 자식 노드로 APPLE를 등록한 후 다음 줄로 넘어간다.

이처럼 탐색을 이어가면 트리 구조를 형성할 수 있고, 루트 노드부터 재귀적으로 출력해준다면 쉽게 풀어갈 수 있을 것이다.

소스코드

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

public class Main {
    static int n;
    static int k;
    static StringTokenizer st;

    static class Node implements Comparable<Node> {
        String name;
        HashMap<String, Node> childrenNode;

        Node(String name) {
            this.name = name;
            childrenNode = new HashMap<>();
        }

        public void addChild(Node child) {
            childrenNode.put(child.name, child);
        }

        @Override
        public int compareTo(Node o) {
            return name.compareTo(o.name);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return Objects.equals(name, node.name);
        }

        @Override
        public int hashCode() {
            return Objects.hashCode(name);
        }
    }

    static void print(int level, Node node) {
        System.out.print("-".repeat(level*2));
        System.out.println(node.name);

        List<Node> nodes = new ArrayList<>(node.childrenNode.values());
        Collections.sort(nodes);

        for (Node n : nodes) {
            print(level + 1, n);
        }
    }


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

        n = Integer.parseInt(br.readLine());


        Node rootNode = new Node("root");

        Node parentNode = null;
        Node childNode = null;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());

            parentNode = rootNode;

            for (int j = 0; j < k; j++) {
                String name = st.nextToken();
                if (!parentNode.childrenNode.containsKey(name)) {
                    childNode = new Node(name);
                    parentNode.childrenNode.put(name, childNode);
                } else {
                    childNode = parentNode.childrenNode.get(name);
                }
                parentNode = childNode;
            }
        }

        List<Node> nodes = new ArrayList<>(rootNode.childrenNode.values());
        Collections.sort(nodes);

        for (Node node : nodes) {
            print(0, node);
        }
    }
}

채점 결과

-를 출력하는 로직을 잘못 봐서 오답이었다.