[BOJ] 7432 - 디스크 트리 (Python, JavaScript)

 

 

아이디어

 

14725번 개미굴과 비슷한 문제로, 트라이를 이용해 디렉토리 구조를 출력한다.

 

 

풀이 #1 (Python)

 

import sys

input = sys.stdin.readline

class Trie():

    def __init__(self):
        self.root = dict()

    def insert(self, directories):
        node = self.root
        for directory in directories:
            if directory not in node:
                node[directory] = dict()
            node = node[directory]

    def search(self):

        def dfs(node, d):
            for directory in sorted(node.keys()):
                res.append(' '*d+directory)
                dfs(node[directory], d+1)

        res = []
        dfs(self.root, 0)
        return res

def solution():
    N = int(input())
    trie = Trie()
    for _ in range(N):
        directories = input().rstrip().split('\\')
        trie.insert(directories)
    print('\n'.join(trie.search()))

solution()

 

 

 

풀이 #2 (JavaScript)

 

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');

class Trie {
    
    constructor() {
        this.root = new Map();
    }
    
    insert(directories) {
        let node = this.root;
        for (const directory of directories) {
            if (!(node.get(directory))) node.set(directory, new Map());
            node = node.get(directory);
        }
    }
    
    search() {
        
        function dfs(node, d) {
            for (const directory of [...node.keys()].sort()) {
                res.push(' '.repeat(d)+directory);
                dfs(node.get(directory), d+1);
            }
        }
        
        let res = [];
        dfs(this.root, 0);
        return res;
    }
}

function solution() {
    const N = Number(input[0]);
    let trie = new Trie();
    for (let i=1; i<=N; i++) {
        const directories = input[i].split('\\');
        trie.insert(directories);
    }
    console.log(trie.search().join('\n'))
}

solution();