백준 5446번 : 용량 부족 - 트라이, Java

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

5446번: 용량 부족

1.문제설명

주어지는 문자열을 바탕으로

트라이를 만들고 각 분기점에 대해 파일들을 한번에 지울 수 있는지 없는지 판별하여

모든 파일을 지우는 최소 횟수를 구해야 하는 문제이다.

 

우선 주어지는 N1개의 단어를 바탕으로 트라이를 구현한 후

지울 수 없는 단어 N2개에 대해서

이미 구현된 트라이에 해당 단어는 지울 수 없음을 마킹한다.

 

마킹이 완료되면 전체 트라이를 순회하면서

해당 분기를 지울 수 있으면 1을 리턴하고,

지울 수 없다면 다음 노드로 이동한다.

 

다음 노드에서도 해당 분기를 지울 수 있으면 1을 리턴하고, 지울 수 없다면

다음 노드로 이동하는 과정을 재귀적 구현한다.

이때 지울 수 없지만 단어의 마지막 지점인 경우에는 1을 더해주어야 한다.

 

2.문제풀이코드 Java

 

//package org.example;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main {
    final int MX = 63;
    final long mod = 1000000007;
 
    public int charToNum(char a) {
        if (a == '.') return 62;
        if (Character.isDigit(a)) { // 0~9
            return a - '0';
        }
        int num = a - 'A';
        if (num >= 26) return a - 'a' + 10;
        return num + 36;
    }
 
    class Trie {
        Trie[] child;
        boolean end;
        boolean canDelete;
 
        public Trie() {
            child = new Trie[MX];
            end = false;
            canDelete = true;
        }
 
        public void insert(String str) {
            Trie tmp = this;
            for (int i = 0; i < str.length(); i++) {
                int cur = charToNum(str.charAt(i));
                if (tmp.child[cur] == null) {
                    tmp.child[cur] = new Trie();
                }
                tmp = tmp.child[cur];
            }
            tmp.end = true;
        }
 
        public void markNotDelete(String str) {
            Trie tmp = this;
 
            for (int i = 0; i < str.length(); i++) {
                int cur = charToNum(str.charAt(i));
                if (tmp.child[cur] == null) {
                    return;
                }
                tmp.child[cur].canDelete = false;
                tmp = tmp.child[cur];
            }
        }
 
        public int getAns() {
            Trie tmp = this;
 
            int ret = 0;
 
            for (int i = 0; i < MX; i++) {
                if (tmp.child[i] != null) {
                    if (tmp.child[i].end && !tmp.child[i].canDelete) {
                        ret++;
                    }
                    if (tmp.child[i].canDelete) {
                        ret++;
                    } else {
                        ret += tmp.child[i].getAns();
                    }
                }
            }
            return ret;
        }
 
    }
 
 
    public void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
 
        for (int T = 0; T < t; T++) {
            int N1 = Integer.parseInt(br.readLine());
 
            Trie root = new Trie();
 
            for (int i = 0; i < N1; i++) {
                String trieInput = br.readLine();
                root.insert(trieInput);
            }
 
            int N2 = Integer.parseInt(br.readLine());
 
            for (int i = 0; i < N2; i++) {
                String notDeleteName = br.readLine();
                root.markNotDelete(notDeleteName);
            }
 
            // root check
            boolean canRmAll = true;
            for (int i = 0; i < MX; i++) {
                if (root.child[i] != null && !root.child[i].canDelete) {
                    canRmAll = false;
                    break;
                }
            }
            if (canRmAll) {
                System.out.println(1);
                continue;
            }
 
            System.out.println(root.getAns());
        }
    }
 
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}