[BOJ] 백준 7432번 디스크 트리 (Java)

#7432 디스크 트리

난이도 : 골드 2

유형 : 트라이

7432번: 디스크 트리

▸ 문제

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

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

▸ 입력

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

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

▸ 출력

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

 

문제 풀이  

트라이 기본 문제이다. 문자열을 트라이 노드에 저장하고 그대로 출력해주면 된다. 한 가지 역슬래시 "\"는 "\\"로 표현되어야 하므로 split할 때 "\\" → "\\\\"로 표현되어야 하는 것만 주의하자.

 

예제로 주어진 데이터는 다음과 같은 트라이 형태가 나오게 된다.

 

 

풀이 코드 

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

public class Main {

	static class TrieNode{
		Map<String, TrieNode> childNode = new HashMap<>();
		
		TrieNode(){
			/* no-op */ 
		}
		
		public void insert(String strs) {
			TrieNode trieNode = this;
			String[] str = strs.split("\\\\");
			for(String s : str) {
				trieNode.childNode.putIfAbsent(s, new TrieNode());
				trieNode = trieNode.childNode.get(s);
			}
		}
		
		public void print(TrieNode cur, int depth) {
			TrieNode trieNode = cur;
			if(trieNode.childNode !=null) {
				List<String> list = new ArrayList<>(trieNode.childNode.keySet());
				Collections.sort(list);
				for(String str : list) {
					for(int i=0; i<depth; i++) {
						System.out.print(" ");
					}
					System.out.println(str);
					print(trieNode.childNode.get(str), depth+1);
				}
			}
			
		}
		
	}
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		TrieNode trie = new TrieNode();
		for(int i=0; i<n; i++) {
			String line = br.readLine();
			trie.insert(line);
		}
		
		trie.print(trie, 0);
		
	}
}