読者です 読者をやめる 読者になる 読者になる

LoL/LJL好きのエンジニアのブログ

技術的な話やら、最近はLoLやLJLの話など。

AOJ 2619: Thread Tree

はじめに

問題訳

ネイサン・O・デイビスは、JAGチャンネルという電子掲示板を運営していた。 彼は、この電子掲示板にスレッドビューを追加したいと思った。

他の掲示板と同じように、JAGチャンネルもスレッド形式になっている。 スレッド(トピックとも呼ばれる)とは、一つの話題を取り扱う複数の投稿の集まりである。 投稿は、新しいスレッドを作成するか、スレッドにある投稿にリプライする形で投稿できる。

スレッドビューは木構造のようなビューで、返信の構造を可視化したものである。 それぞれの投稿は木のノードで、サブノードとして、その投稿へのリプライを 古いものから順番に持つ。

例えば、あるユーザが'hoge'と投稿した。 他のユーザが、それに'fuga'とリプライした。 さらに他のユーザが'hoge'に対して'piyo'とリプライした。 'fuga'に対して、'foobar', 'jagjag' とリプライされた。 この場合の木構造は以下の通りである。

(原文の図参照)

実装を簡単にするために、ネイサンは簡単な形式を考えた。 それぞれの投稿の深さをドットで表す。 リプライはその親の投稿よりも1つドットが多くなる。 先ほどの木構造をこの形式で表すと以下のようになる。

(原文の図参照)

あなたには、このように、1つのスレッドを木構造を表示するプログラムを書いてもらいたい

入力

一番最初の行の整数  n (1 \leq n \leq 1,000) はこのスレッドの投稿の数である。 それぞれの投稿は2行で表される。 1行目は整数  k_i  (k_1 = 0, 1 \leq k_i < i) であり、 これは、 i番目の投稿は  k_i番目の投稿へのリプライであることを表している。 2行目は文字列  M_i で、これは投稿の内容である。  k_1 は常に0で、これはどの投稿にもリプライしていないことを表す。 この投稿が最初の投稿である。

投稿の内容は1文字以上50文字以下で、英数字の列である。

出力

問題文に示したような図を出力せよ

実装

  • 木構造を実装すれば良いが、子ノードは順番を持つことに注意。
  • ハッシュでノードを管理し、リプライ先が取得できるようにする。
  • 最終的に再帰的にprintしていく
class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        HashMap<Integer, Node> map = new HashMap<Integer, Node>();
        Node root = null;
                
        for (int i = 1; i <= n; i++) {
            int k = Integer.parseInt(br.readLine());
            String m = br.readLine();
            Node node = new Node(m);
            
            // 親を持つ場合その親の子に追加
            if(k != 0){
                Node parent = map.get(k);
                parent.addChild(node);
                node.depth = parent.depth + 1;
            }else{
                root = node;
                node.depth = 0;
            }
            
            map.put(i, node);
        }
        root.print();
    }
}


class Node{
    ArrayList<Node> children = new ArrayList<Node>();
    String message;
    int depth;
    Node(String message){
        this.message = message;
    }
    public void addChild(Node n){
        children.add(n);
    }
    // 再帰的print
    public void print(){
        StringBuffer buf = new StringBuffer();
        for(int i = 0; i < depth; i++)
            buf.append('.');
        buf.append(message);
        System.out.println(buf.toString());
        
        for(int i = 0; i < children.size(); i++)
            children.get(i).print();
    }
}

余談

Sample Input がラブライブだったりする

f:id:yoshiki_utakata:20150523090732p:plain