[BaekJoon] 7432번 - 디스크 트리 [Java][C++]

문제 링크

---

1. 문제 풀이

BaekJoon 14725번 - 개미굴 문제와 동일한 아이디어로 해결할 수 있다. 역슬래시 파싱에만 주의하면 된다.

---

2. 코드

1. 풀이 [Java]

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

public class Main {

    static StringBuilder sb = new StringBuilder();
    static final int MX = 1 + 500 * 80;
    static final int ROOT = 0;
    static int unused = ROOT + 1;
    static Map<String, Integer>[] nxt = new TreeMap[MX];

    static {
        for (int i = 0; i < MX; i++) {
            nxt[i] = new TreeMap<>();
        }
    }

    static void insert(String[] words) {
        int cur = ROOT;
        for (String word : words) {
            if (!nxt[cur].containsKey(word)) nxt[cur].put(word, unused++);
            cur = nxt[cur].get(word);
        }
    }

    static void dfs(int cur, int depth) {
        for (Map.Entry<String, Integer> entry : nxt[cur].entrySet()) {
            sb.append(" ".repeat(depth)).append(entry.getKey()).append("\n");
            dfs(entry.getValue(), depth + 1);
        }
    }

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

        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            String[] words = br.readLine().split("\\\\");
            insert(words);
        }

        dfs(ROOT, 0);

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 500 * 80;
const int ROOT = 0;
int unused = ROOT + 1;
map<string, int> nxt[MX];

void insert(auto& v) {
    int cur = ROOT;
    for (string& s : v) {
        if (nxt[cur][s] == 0) nxt[cur][s] = unused++;
        cur = nxt[cur][s];
    }
}

void print(int cur, int depth) {
    for (auto& [k, v] : nxt[cur]) {
        for (int i = 0; i < depth; i++) {
            cout << " ";
        }
        cout << k << '\n';
        print(v, depth + 1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    cin.ignore();

    while (n--) {
        string line;
        getline(cin, line);

        vector<string> v;
        string s;

        for (char c : line) {
            if (c == '\\') {
                v.push_back(s);
                s.clear();
            } else {
                s += c;
            }
        }
        v.push_back(s);

        insert(v);
    }

    print(ROOT, 0);
}

---