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

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

7432번: 디스크 트리

 

 

이번 포스팅에서는 트라이를 순회하는 문제에 대해 다뤄보도록 하겠다.

 

이전 포스팅에서도 언급한적이 있듯

키 집합으로 하위노드가 정렬된 트라이로 생성한다면

전위순회를 통해 사전순으로 저장된 데이터를 출력할수 있다.

 

그럼 바로 문제 분석으로 들어가도록 하겠다.

 

여러줄로 디렉토리경로가 주어지고 경로의 구분자는 \ (역슬래시)로 한다.

이를 하위 디렉토리라면 한칸씩 띄운뒤 사전순으로 출력해주면 된다.

 

핵심 아이디어는 키집합으로 하위노드가 정렬된 트라이로 생성하기 위해서

TreeMap 자료구조를 사용하는것이다. 

TreeMap은 기본적으로 데이터를 오름차순으로 정렬해 저장하므로 

하위노드를 저장할 자료구조로 적합하다.

 

그럼 바로 코드로 풀이해보도록 하겠다.

 

먼저 트라이의 노드를 클래스로 선언해주도록 하겠다.

필드로 TreeMap으로 저장할 자식노드를 갖고,

데이터를 추가하는 메소드와 자식노드집합을 가져올 메소드를 선언해준다.

 

class Directory {
	
	private TreeMap<String,Directory> child;
	
	Directory add(String name) {
		if(child == null) { child = new TreeMap<>(); }
		if(!child.containsKey(name)) { child.put(name, new Directory()); }
		return child.get(name);
	}
	
	TreeMap<String,Directory> getChild() { return child; }
	
}

 

이때 map은 key로 각 디렉토리의 이름으로 구분을 하며 value로 노드를 갖도록해 재귀적으로

트라이를 생성해줄것이다.

 

이제 트라이를 생성할 클래스를 선언해주겠다.

필드로 루트와 입력받은 문자열을 구분자로 잘라낼 StringTokenizer 객체를 갖도록 한다.

 

class DirectoryTrie {
	
	private Directory root;
	private StringTokenizer st;
}

 

 

다음은 생성자 부분이다.

생성자에서는 루트노드에 객체를 생성해주도록 한다.

 

	DirectoryTrie(){ root = new Directory(); }

 

 

삽입 메소드에서는 인자로 받은 문자열을 StringTokenizer 객체의 인자값으로 주어

구분자로 잘라낼수 있도록 한다.

그리고 잘라낸 문자열을 루트부터 더이상 잘라낼 문자열이 없을때까지 트라이에 저장한다.

 

	void insert(String text) {
		st = new StringTokenizer(text,"\\");
		insertProcess(root.add(st.nextToken()));
	}
	
	private void insertProcess(Directory node) {
		if(!st.hasMoreTokens()) return;
		insertProcess(node.add(st.nextToken()));
	}

 

 

이제 전위 순회를 통해 사전순으로 저장된 각 노드들을 순차적으로 줄바꿈과 간격으로 구분을 해서

출력할 문자열로 리턴해주는 메소드를 선언해주도록 하겠다.

 

	String preOrder() {
		StringBuilder sb = new StringBuilder();
		preOrderProcess(root,sb,0);
		return sb.toString();
	}
	
	private void preOrderProcess(Directory node, StringBuilder sb,int depth) {
		TreeMap<String,Directory> child = node.getChild();
		if(child == null) { return; }
		child.keySet().forEach(k -> {
			for(int i = 0; i < depth; i++) {
				sb.append(' ');
			}
			sb.append(k).append('\n');
			preOrderProcess(child.get(k),sb,depth + 1);
		});
		
	}

 

 

인자로 깊이를 의미하는 변수 depth를 같이 넘겨주어 깊어지는 만큼 간격을 추가할수 있도록 했다.

 

 

이제 입력조건에 따라 입력을 받아 실행하게 되면,

정확한 답을 내는것을 볼 수 있다.

 

 

아래는 코드의 전문이다.

 

package boj5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Boj7432 {
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		DirectoryTrie trie = new DirectoryTrie();
		int n = Integer.parseInt(in.readLine());
		
		while(n-- > 0) {
			trie.insert(in.readLine());
		}
		
		in.close();
		
		System.out.print(trie.preOrder());
	}

}

class Directory {
	
	private TreeMap<String,Directory> child;
	
	Directory add(String name) {
		if(child == null) { child = new TreeMap<>(); }
		if(!child.containsKey(name)) { child.put(name, new Directory()); }
		return child.get(name);
	}
	
	TreeMap<String,Directory> getChild() { return child; }
	
}

class DirectoryTrie {
	
	private Directory root;
	private StringTokenizer st;
	
	DirectoryTrie(){ root = new Directory(); }
	
	void insert(String text) {
		st = new StringTokenizer(text,"\\");
		insertProcess(root.add(st.nextToken()));
	}
	
	private void insertProcess(Directory node) {
		if(!st.hasMoreTokens()) return;
		insertProcess(node.add(st.nextToken()));
	}
	
	String preOrder() {
		StringBuilder sb = new StringBuilder();
		preOrderProcess(root,sb,0);
		return sb.toString();
	}
	
	private void preOrderProcess(Directory node, StringBuilder sb,int depth) {
		TreeMap<String,Directory> child = node.getChild();
		if(child == null) { return; }
		child.keySet().forEach(k -> {
			for(int i = 0; i < depth; i++) {
				sb.append(' ');
			}
			sb.append(k).append('\n');
			preOrderProcess(child.get(k),sb,depth + 1);
		});
		
	}
	
	
}