[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를 두번 탐색하지 않기 때문이다.)
Author And Source
이 문제에 관하여([7432]디스크 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@away0419/7432디스크-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)