[백준 7432] 디스크 트리(java)

문제

갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파일이 걱정되기 시작했다. 다행히 상근이는 저장되어 있는 중요한 디렉토리의 전체 경로를 텍스트 파일로 따로 저장하고 있었다. 예를 들면, WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86.

상근이의 중요한 디렉토리의 전체 경로가 모두 주어졌을 때, 디렉토리 구조를 구해 보기 좋게 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 중요한 디렉토리 전체 경로의 개수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개 줄에는 디렉토리 경로가 주어진다. 경로는 한 줄로 이루어져 있으며, 공백을 포함하지 않는다. 경로는 80글자를 넘지 않으며, 디렉토리는 역슬래시()로 구분된다.

각 디렉토리의 이름은 1~8글자이며, 알파벳 대문자, 숫자, 특수 문자로 이루어져 있다. 디렉토리 이름에 들어있을 수 있는 특수문자는 !#$%&'()-@^_`{}~ 이다.

출력

디렉토리 구조를 보기 좋게 출력한다. 한 줄에 하나씩 디렉토리의 이름을 출력하며, 공백은 디렉토리 구조상에서 깊이를 의미한다. 각 서브 디렉토리는 사전순으로 출력해야 하며, 부모 디렉토리에서 출력한 공백의 개수보다 1개 많게 공백을 출력한다. 예제 출력을 보면서 형식을 참고하는 것이 좋다.

문제 풀이

트리를 이용하여 풀었다.

먼저 사전순으로 입력을 해야되서 

입력되는 스트링들을 먼저 소팅했다.

 

하지만 소팅을 할때 문제가 있다.

그냥 소팅을 하면 

WINNT\SYSTEM32\CONFIG

WIN\SOFT

위의 두 스트링중에 WINNT가 앞에 오게된다. 

 

그래서 "\"를 " "로 치환해준다. 

하지만 치환해주는 코드는

String s = str.replaceAll("\\\\"," ");

치환해주는 코드는 위와 같은데 

자바에서는 \를 \\로 인식하는데 \\를 " "로 변경해야되니

위와같이 치환을 해주어야 됩니다.

 

그리고는 트리를 만들고 출력해주었습니다.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;
 
 
 
public class Baekjoon7432 {
 
    static int numOfDir;
    static Tree tree ;
 
 
    public static void main(String[] args) throws IOException {
        inputData();
 
    }
 
    public static void inputData() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        numOfDir = Integer.parseInt(br.readLine());
        tree = new Tree();
        TreeNode root = tree.getRoot();
        ArrayList<String> inputString = new ArrayList<>();
        for(int i=0;i<numOfDir;i++){
            String str = br.readLine();
            String s = str.replaceAll("\\\\"," ");
            inputString.add(s);
        }
        Collections.sort(inputString);
 
        for(String str : inputString){
            //System.out.println(str);
            StringTokenizer st = new StringTokenizer(str," ");
            ArrayList<String> paths = getDirPath(st);
            tree.insertNewDirectory(paths,0,root);
        }
        tree.printTree(root,-1);
 
    }
 
    public static ArrayList<String> getDirPath(StringTokenizer st) {
        ArrayList<String> paths = new ArrayList<String>();
        while(st.hasMoreTokens()){
            paths.add(st.nextToken());
        }
        return paths;
    }
 
    static class TreeNode{
        private int level;
        private String directoryName;
        private ArrayList<TreeNode> child;
 
        public TreeNode(int level){
            this.level = level;
            this.child = new ArrayList<>();
        }
        public TreeNode(int level, String directoryName) {
            this.level = level;
            this.directoryName = directoryName;
            this.child = new ArrayList<TreeNode>();
        }
        public TreeNode getLastChildNode(){
            int childSize = child.size();
            return child.get(childSize-1);
        }
    }
 
    static class Tree{
        TreeNode root;
 
        public Tree() {
            root = new TreeNode(-1);
            this.root = root;
        }
 
        public TreeNode getRoot() {
            return root;
        }
 
        public void insertNewDirectory(ArrayList<String> paths, int level, TreeNode curNode){
            if(level>=paths.size())
                return;
            for(TreeNode child : curNode.child){
                if(child.directoryName.equals(paths.get(level))){
                    insertNewDirectory(paths,level+1,child);
                    return;
                }
            }
            //이까지 왔으면 없던 dir
            curNode.child.add(new TreeNode(level,paths.get(level)));
            insertNewDirectory(paths,level+1, curNode.getLastChildNode());
        }
 
        public void printTree(TreeNode curNode,int level){
            if(curNode.child.isEmpty()){
                printDir(curNode, level);
                return;
            }else{
                if(level!=-1){
                    printDir(curNode, level);
                }
            }
            for(TreeNode child : curNode.child){
                printTree(child,level+1);
            }
        }
 
        public void printDir(TreeNode curNode, int level) {
            String space = "";
            for (int i = 0; i < level; i++) {
                space += " ";
            }
            System.out.println(space + curNode.directoryName);
        }
 
    }
 
}
 

 

문제 링크 : www.acmicpc.net/problem/7432

7432번: 디스크 트리