[백준] 7432번 : 디스크 트리 - 자바(JAVA)

https://www.acmicpc.net/problem/7432

7432번: 디스크 트리

 

문제 해석

디렉토리의 경로가 주어졌을때, 디렉토리 구조를 보기 좋게 출력하는 프로그램을 작성하세요

공백은 디렉토리 구조상 깊이를 의미하며 서브 디렉토리는 사전순으로 출력해야 합니다.

입력의 값을 토대로 디렉토리 구조를 유추하는 문제입니다.

 

문제 풀이 전 설계

우선 \ 라는 역슬래시로 디렉토리가 구분됩니다.

계층구조를 가져야 하기 때문에 트리구조? (부모, 자식)을 활용하여 디렉토리 구조를 만들고 같은 레벨이라면 사전순으로 먼저 출력합니다.

단, 부모는 유일하더라도 자식은 여러개일 수 있습니다.

 

문제 풀이 하면서

트라이 자료구조라는걸 공부하면서 풀이해 보았습니다.

https://junuuu.tistory.com/261?category=987844 

트라이 자료구조

 

비슷한 형식으로 /를 하나의 단어로 보고 루트부터 디렉토리를 트리구조로 만들어 갔습니다.

 

삽입을 할때는 현재 Map에 해당 String이 들어가있다면 자식으로 이동하였으며 존재하지 않는다면 현재에 String을 넣어주고 자식으로 이동하였습니다.

 

출력할때는 루트부터 탐색하여 만약 자식의 크기가 > 0 이라면 DFS로 탐색을 쭉 해줬습니다.

 

코드

import org.junit.jupiter.api.Test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.SortedMap;
import java.util.TreeMap;

public class Main_7432_디스크트리 {
    static StringBuilder sb = new StringBuilder();

    static class Node {
        SortedMap<String, Node> childs;

        public Node(SortedMap<String, Node> childs) {
            this.childs = childs;
        }

        public void insert(String value){
            String[] splited = null;
            //example value = "WINNT\SYSTEM32\CONFIG"
            //splited = value.split("[^A-Z0-9!#$%&'()-@^_`{}~]");

            //들어온 문자열 value \를 구분자로 split
            splited = value.split("\\\\");
            //계층적으로 들어가기 위한 현재Map을 갱신하기 위해 선언 시작은 root
            SortedMap<String,Node> curMap = this.childs;

            for(String cur : splited){
                //만약 현재Map에 string이 들어가있다면
                if(curMap.containsKey(cur)) {
                    //계층적으로 depth를 한번 들어감
                    curMap = curMap.get(cur).childs;
                    continue;
                }
                //만약 현재Map에 stirng이 들어가 있지 않다면 현재에 넣어주고 다음 삽입을 위해 계층적으로 한칸 들어감
                SortedMap tempMap = new TreeMap<String,Node>();
                curMap.put(cur, new Node(tempMap));
                curMap = tempMap;

            }
        }

        public void print(SortedMap<String, Node> curMap, int count) {
            for(String strKey : curMap.keySet()){
                for (int i = 0; i < count ; i++) {
                    sb.append(" ");
                }
                sb.append(strKey + "\n");
                if(curMap.get(strKey).childs.size() !=0){
                    print(curMap.get(strKey).childs , count+1);
                }
            }
        }
    }

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

        String temp = null;
        Node root = new Node(new TreeMap<>());

        for(int i=0; i<N; i++){
            temp = br.readLine();
            root.insert(temp);
        }
        //트리 생성 끝
        
        //트리 root부터 사전순으로 출력
        root.print(root.childs, 0);
        System.out.print(sb.toString());
    }

    @Test
    public void splitedTest() {

        String given = "WINNT\\SYSTEM32\\CERTSRV\\CERTCO~1\\X86";
        String[] splited = given.split("[^A-Z0-9!#$%&'()-@^_`{}~]");

        System.out.println(given);
        for (String cur : splited){
            System.out.println(cur);
        }
    }
}