문제
개미굴의 구조를 파악하기 위해 로봇 개미를 투입한다. 로봇 개미가 돌아오면서 수집한 정보가 N개 주어진다. 각 정보는 로봇이 방문한 방의 경로(최상위 방부터 순서대로)이며, 각 방의 이름은 알파벳 대문자로 이루어진 문자열이다.
이 정보를 바탕으로 개미굴의 트리 구조를 출력하라. 같은 깊이에서는 방 이름을 사전순으로 출력하고, 들여쓰기는 깊이마다 --를 붙인다.
입력
첫 번째 줄에 로봇 개미가 돌아온 횟수 N이 주어진다. (1 ≤ N ≤ 1,000)
이후 N줄에 걸쳐 각 줄의 첫 번째 숫자는 경로의 방 개수 K이고, 이후 K개의 문자열이 방 이름으로 주어진다. (1 ≤ K ≤ 15, 방 이름 길이 ≤ 20)
출력
개미굴의 트리 구조를 출력한다. 루트는 출력하지 않으며, 각 자식 노드는 (깊이-1)*"--" 만큼 들여쓰기 후 이름을 출력한다.
예제
3
2 NUNO LEMMON
2 NUNO GRAPE
3 ANT GRAPE BERRY출력:
ANT
--GRAPE
----BERRY
NUNO
--GRAPE
--LEMMON풀이
핵심 아이디어: 트라이(Trie) 자료구조를 HashMap으로 구현한다. 각 노드는 자식 노드들을 HashMap<String, Node> 형태로 관리한다. 입력으로 받은 각 경로를 루트부터 순서대로 트라이에 삽입하고, 출력 시 각 노드의 자식들을 알파벳 사전순으로 정렬하여 DFS로 출력한다.
- 루트 Node를 생성하고, 각 로봇 경로를 순서대로 트라이에 삽입한다.
- 현재 노드에 해당 방 이름의 자식이 없으면 새 Node를 생성하여 추가한다.
- 출력 시
print(root, "")재귀 함수로 DFS 탐색한다. - 각 레벨에서 자식 키들을
Arrays.sort로 정렬 후 출력하고, 재귀 호출 시bar + "--"를 전달한다.
코드
package day349;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Day314BOJ14725개미굴 {
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
StringTokenizer st;
Node root = new Node();
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int size = Integer.parseInt(st.nextToken());
Node cur = root;
for (int j = 0; j < size; j++) {
String s = st.nextToken();
if (!cur.childs.containsKey(s)) {
cur.childs.put(s, new Node());
}
cur = cur.childs.get(s);
}
}
print(root, "");
}
public static void print(Node root, String bar) {
Object[] key = root.childs.keySet().toArray();
Arrays.sort(key);
for (Object s : key) {
System.out.println(bar + s);
print(root.childs.get(s), bar + "--");
}
}
}
class Node {
HashMap<String, Node> childs = new HashMap<>();
}복잡도
- 시간: O(N × K × L × log(N×K)) — 삽입 O(N×K×L), 출력 시 정렬 O(각 레벨 자식 수 × log × L)
- 공간: O(N × K × L) — 트라이에 저장된 총 문자열 길이 (N: 경로 수, K: 경로 길이, L: 방 이름 길이)