백준 - 디스크 트리 (7432) : JAVA

문제 유형
트리, TreeMap, dfs

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파일이 걱정되기 시작했다. 다행히 상근이는 저장되어 있는 중요한 디렉토리의 전체 경로를 텍스트 파일로 따로 저장하고 있었다. 
2. 예를 들면, WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86. 
상근이의 중요한 디렉토리의 전체 경로가 모두 주어졌을 때, 3. 디렉토리 구조를 구해 보기 좋게 출력하는 프로그램을 작성하시오.
4. 디렉토리 구조를 보기 좋게 출력한다. 한 줄에 하나씩 디렉토리의 이름을 출력하며, 공백은 디렉토리 구조상에서 깊이를 의미한다. 각 서브 디렉토리는 사전순으로 출력해야 하며, 부모 디렉토리에서 출력한 공백의 개수보다 1개 많게 공백을 출력한다. 

트리의 전체적인 이해만 있다면 쉽게 해결할 수 있는 문제입니다.

class Node {
	String key;
	int height;
	TreeMap<String, Node> children = new TreeMap<>((n1,n2)-> n1.compareTo(n2));
	
	Node(String key, int height) {
		this.key = key;
		this.height = height;
	}
}

평균 O(1)의 시간복잡도를 자식 노드를 탐색하고, 오름차순으로 트리를 출력하기 위해서 TreeMap에 자식 노드들을 저장합니다.

for (int i = 0; i < n; i++) {
    String path = br.readLine();

    String[] dir = path.split("\\\\");


    if (!tree.containsKey(dir[0])) {

        Node root = new Node(dir[0], 0);

        tree.put(dir[0], root);

        insert(root, dir, 1, dir.length);
    } else {

        Node root = tree.get(dir[0]);


        Node cur = findLeaf(root, dir, 1, dir.length);
        insert(cur, dir, cur.height + 1, dir.length);
    }
}

\는 escape 문자이기 때문에 \\\\로 \를 표현해야합니다.
첫 문자열이 root 노드의 키로 주어지기 때문에 이미 tree에 저장되어있는 키라면 findLeaf를 통해 리프 노드를 찾아 insert를 진행합니다.
이미 tree에 저장되어있는 키가 아니라면 처음부터 insert를 진행합니다.

static Node findLeaf(Node cur, String[] dir, int num, int len) {

    if (num >= len) {
        return cur;
    }

    String key = dir[num];

    if (cur.children.containsKey(key)) {
        return findLeaf(cur.children.get(key), dir, num + 1, len);
    } else {
        return cur;
    }
}

static void insert(Node cur, String[] dir, int num, int len) {

    if (num >= len) return;

    Node child = null;

    if (!cur.children.containsKey(dir[num])) {
        child = new Node(dir[num], num);
        cur.children.put(dir[num], child);
    } else {
        child = cur.children.get(dir[num]);
    }

    insert(child, dir, num + 1, len);


}

findLeaf와 insert 메서드는 위와 같습니다.

static void printTree(Node cur, StringBuilder sb) {

    for (int i = 0; i < cur.height; i++) sb.append(" ");
    sb.append(cur.key).append("\n");

    for (Map.Entry < String, Node > entry: cur.children.entrySet()) {
        printTree(entry.getValue(), sb);
    }


}

트리를 출력하는 것은 dfs를 사용했습니다.
전위순회의 특성을 갖기 때문입니다. (자식 -> 서브트리 순으로 출력)

시간 복잡도
O(N^2)

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


class Node {
	String key;
	int height;
	TreeMap<String, Node> children = new TreeMap<>((n1,n2)-> n1.compareTo(n2));
	
	Node(String key, int height) {
		this.key = key;
		this.height = height;
	}
}

public class Main {
	
	static TreeMap<String, Node> tree  = new TreeMap<>((n1,n2)-> n1.compareTo(n2));
	
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        
        for (int i=0; i<n; i++) {
        	String path = br.readLine();
        	
        	String[] dir = path.split("\\\\");
        	
        	
        	if(!tree.containsKey(dir[0])) {
        		
        		Node root = new Node(dir[0], 0);
        		
        		tree.put(dir[0], root);
        		
        		insert(root, dir, 1, dir.length);
        	}
        	else {
        		
        		Node root = tree.get(dir[0]);
        		
        		
        		Node cur = findLeaf(root, dir, 1, dir.length);
        		insert(cur, dir, cur.height+1, dir.length);
        	}
        	
    
        }
        
        
        for (Map.Entry<String, Node> entry : tree.entrySet()) {
        	Node root = entry.getValue();
        	
        	StringBuilder sb = new StringBuilder();
        	printTree(root, sb);
        	sb.deleteCharAt(sb.length()-1);
        	System.out.println(sb.toString());
        }
        
       

    }
    
    static void printTree(Node cur, StringBuilder sb) {
    	
    	for (int i=0; i<cur.height; i++) sb.append(" ");
    	sb.append(cur.key).append("\n");
    	
    	for (Map.Entry<String, Node> entry : cur.children.entrySet()) {
    		printTree(entry.getValue(), sb);
		}
    	
    	
    }
    
    
    static Node findLeaf(Node cur, String[] dir, int num, int len) {
    	
    	if (num >= len) {
    		return cur;
    	}
    	
    	String key = dir[num];
    
    	if (cur.children.containsKey(key)) {
    		return findLeaf(cur.children.get(key), dir, num+1, len);
    	}
    	else {
    		return cur;
    	}
    }
    
    static void insert(Node cur, String[] dir, int num, int len) {
    	
    	if (num >= len) return;
    	
    	Node child = null;
    	
    	if (!cur.children.containsKey(dir[num])) {
    		child = new Node(dir[num], num);
    		cur.children.put(dir[num], child);
    	}
    	else  {
    		child = cur.children.get(dir[num]);
    	}
    	
    	insert(child, dir, num+1, len);
    	
    	
    }

}