BOJ_14725_개미굴

리스트와 정렬로 풀었지만 트라이(Trie)를 사용하는 문제였다

1. 리스트 + 정렬

package BJO;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.function.Function;

public class BJO_14725_개미굴 {

 static class Fruit implements Comparable<Fruit> {
     String name;
     List<Fruit> child = new ArrayList<>();

     public Fruit(String name) {
         this.name = name;
     }

     @Override
     public String toString() {
         return this.name;
     }

     @Override
     public int compareTo(Fruit o) {
         return this.name.compareTo(o.name);
     }
 }

 static List<List<Fruit>> list;
 static Function<String, Integer> parsing = Integer::parseInt;

 public static void main(String[] args) throws IOException {
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     int N =parsing.apply(br.readLine());
     list = new ArrayList<>();
     StringTokenizer st;

     for (int i = 0; i < N; i++) {
         st = new StringTokenizer(br.readLine());
         int K = parsing.apply(st.nextToken());

         Fruit parent = null;
         for (int j = 0; j < K; j++) {
             if (list.size() <= j) {
                 list.add(new ArrayList<>());
             }

             // 상수로 간주하는 변수
             String NAME = st.nextToken();
             int IDX = j;
             Fruit PARENT = parent;

             parent = isFruitEmpty(IDX, NAME, PARENT).orElseGet(() -> {
                 Fruit newFruit = new Fruit(NAME);
                 list.get(IDX).add(newFruit);

                 if (IDX > 0) {
                     PARENT.child.add(newFruit);
                 }
                 return newFruit;
             });
         }
     }

     Collections.sort(list.get(0));
     for (int i = 0; i < list.get(0).size(); i++) {
         printDfs(0, list.get(0).get(i));
     }
 }

 static Optional<Fruit> isFruitEmpty(int j, String name, Fruit parent) {
     return list.get(j).stream().filter(fruit -> fruit.name.equals(name) && (parent == null || parent.child.contains(fruit))).findAny();
 }

 static void printDfs(int depth, Fruit fruit) {
     String minus = "--".repeat(depth);
     System.out.println(minus + fruit.name);

     Collections.sort(fruit.child);
     for (int i = 0; i < fruit.child.size(); i++) {
         printDfs(depth + 1, fruit.child.get(i));
     }
 }
}

구상했던 풀이법은 1) 노드 클래스를 만든 후 2) 각 층을 List로 구현해서 3) 1층 노드 전체를 탐색하며 자식을 정렬해 출력하는 것이었다
입력을 받는 즉시 해당 층의 노드 정보를 탐색해서 만약 노드가 존재하지 않으면 층에 배치하고 부모에게 자식 정보를 넣어준다
List는 노드의 존재 여부 확인을 위해 필요할 뿐이며, 정답을 출력할 때는 각 노드의 child 리스트를 깊이 우선 탐색(DFS)으로 탐색해서 출력한다

96%에서 오답이 떴었는데, 아무 생각 없이 문자열을 사전순으로 정렬할 때 charAt(0)으로 비교했다. compareTo를 쓰니까 맞았다

배운 것

람다식을 쓸 때 값이 변경되는 변수를 쓰니 오류가 났다. 람다 표현식이나 익명 클래스에서 외부 변수를 사용할 때는 해당 변수가 초기화된 이후에 값이 변경되지 않는 effective final 이어야 한다. 그렇지 않다면 임시 변수를 만들어서 쓸 수 있다
String 문자열을 반복하고 싶으면 .repeat(횟수)를 사용한다

2. 트라이(Trie)

하지만~~ 사실 trie 자료 구조를 사용하는 문제라고 한다~~
그래서 트라이로 다시 풀어봤다. 트라이 자료 구조는 자료의 순서가 중요하기 때문에 TreeMap을 사용했다

package BJO;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.function.Function;

public class BJO_14725_개미굴_trie사용 {
 static class Trie {
     Map<String, Trie> child;

     Trie() {
         this.child = new TreeMap<>();
     }

     void print(int depth) {
         for (Map.Entry<String, Trie> entry : child.entrySet()) {
             System.out.println("--".repeat(depth) + entry.getKey());
             entry.getValue().print(depth + 1);
         }
     }
 }

 static int N;
 static Function<String, Integer> parsing = Integer::parseInt;

 public static void main(String[] args) throws IOException {
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
     N = parsing.apply(br.readLine());
     StringTokenizer st;

     Trie root = new Trie();
     for (int i = 0; i < N; i++) {
         st = new StringTokenizer(br.readLine());
         int K = parsing.apply(st.nextToken());

         Trie node = root;
         for (int j = 0; j < K; j++) {
             node = node.child.computeIfAbsent(st.nextToken(), s -> new Trie());
         }
     }

     root.print(0);
 }
}

배운 것

computIfAbsent(찾고 싶은 키, s -> 존재하지 않을 때 키에 할당할 value)