[7432]디스크 트리

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		
		//최상위 폴더
		Path root = new Path();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), "\\");
			
			//현재 폴더를 담는 변수. 처음엔 root
			Path p = root;
			
			while (st.hasMoreTokens()) {
				//폴더명 가져옴
				String s = st.nextToken();
				
				//만약 s(하위폴더명)가 p(현재폴더)의 하위 폴더에 있을 경우
				if (p.map.containsKey(s)) {
				
					//현재 폴더를 하위 폴더 s로 바꾼다.
					p = p.map.get(s);
				
				} else {
					//새로운 폴더를 생성한다.(새롭게 생성된 폴더에는 하위 폴더가 없다.)
					Path pa = new Path();
					
					//생성한 폴더를 현재 폴더에 넣는다.
					p.map.put(s, pa);
					
					//현재 폴더를 하위 폴더인 pa로 바꾼다.
					p = pa;
				}
			}
		}

		fn(root, "");

		System.out.println(sb);

	}

	//주어진 폴더를 탐색하여 하위 폴더를 순서대로 탐색하고, 탐색한 하위 폴더의 하위 폴더를 다시 탐색하는 재귀 함수.  
	static void fn(Path path, String tap) {

		//현재 폴더에 있는 하위 폴더를 순서대로 탐색한다.
		for (String s : path.map.keySet()) {
		
			//tap(깊이와 동일한 띄어쓰기) + 하위 폴더명 + 한줄띄기
			sb.append(tap).append(s).append("\n");
			
			//하위폴더를 기준으로 탐색
			fn(path.map.get(s), tap + " ");
		}
	}

	//현재 폴더를 의미하며 하위 폴더를 map으로 가지는 객체
	static class Path {
		//map : 1단계 하위 폴더들의 집합
		//TreeMap으로 사전순 정렬
		Map<String, Path> map = new TreeMap<>();

	}
}

이 문제는 저장된 단어에서 겹치는 단어를 찾는게 아니기 때문에 굳이 character로 map을 구성하지 않고 풀 수 있다. 그래도 character로 설정하여 풀면 시간이 더욱 단축 될 것이다.
(String으로 할 경우 asdf, asdfg 가 있을때 겹치는 부분인 asdf를 두번 돌기 때문임.
character로 한다면 asdf까지 탐색후 boolean 체크하고 boolean의 상태 여부와 상관 없이 하위 문자들을 찾아 나가므로 asdf를 두번 탐색하지 않기 때문이다.)

좋은 웹페이지 즐겨찾기