[BaekJoon] 5446번 - 용량 부족 [Java][C++]

문제 링크

---

1. 문제 풀이

지워야 하는 파일들과 지우면 안 되는 파일들이 주어졌을 때 최소한의 삭제 명령으로 지워야 하는 파일들을 모두 지워야 하는 문제다. 트라이 자료구조를 활용하면 해결할 수 있는데 먼저 지워야 하는 파일들로 트라이를 만들어준다. 이때 생성 과정에서 방문한 모든 각 노드에 매번 +1을 해줘서 각 노드가 자신까지를 접두어로 갖는 단어의 수를 알 수 있게 해줬고 단어의 끝 역시 표시해줬다. 이후 지우면 안되는 파일들에 대해 현재 트라이에서 접두어가 존재하면 지우면 안된다는 마킹을 해줬다.

이후 루트 노드에서 DFS 탐색을 하면 되는데 최소한의 삭제 명령은 현재 노드의 자식 노드들에 대해 자식 노드가 지우면 안된다고 마킹되지 않았다면 해당 위치에서 와일드 카드로 전부 지울 수 있으므로 한번의 명령만 하면 된다. 자식 노드가 지우면 안된다고 마킹됐다면 다시 재귀를 보낸 결과를 받아서 반환하면 된다. 이를 위해 sum 변수에 재귀를 보낸 후 반환값과 와일드 카드를 사용해서 +1 한 값들을 담았다가 반환했으며 현재 노드가 지우면 안된다고 마킹은 됐지만 지워하 하는 단어면 와일드 카드 없이 해당 단어를 rm으로 삭제해야하므로 이것도 하나를 세줬다.

예제 입력 1을 예로 들면 파란색으로 칠한 칸이 삭제해야 하는 단어의 끝, 빨간색으로 칠한 칸이 삭제하면 안되는 단어의 접두어, 노란색 칸은 파란색과 빨간색이 모두 칠해진 칸이며 체크 표시한 위치에서 해당 노드까지 포함한 접두어와 와일드 카드의 조합으로 삭제 명령을 내리면 된다.

---

2. 코드

1. 풀이 [Java]

import java.io.*;

public class Main {

    static final int MX = 1 + 1000 * 20;
    static final int ROOT = 0;
    static int unused;
    static int[][] nxt;
    static boolean[] chk;
    static int[] cnt;  // 해당 노드의 자손 노드(해당 노드 포함) 중 지워야 하는 파일의 수
    static boolean[] mark;  // 지우면 안되는 파일의 접두어에 해당하는 노드들 체크

    static void init() {
        unused = ROOT + 1;
        nxt = new int[MX][128];
        chk = new boolean[MX];
        cnt = new int[MX];
        mark = new boolean[MX];
    }

    static void insert(String s) {
        int cur = ROOT;
        for (char c : s.toCharArray()) {
            if (nxt[cur][c] == 0) nxt[cur][c] = unused++;
            cur = nxt[cur][c];
            cnt[cur]++;
        }
        chk[cur] = true;
    }

    static void check(String s) {
        int cur = ROOT;
        for (char c : s.toCharArray()) {
            if (nxt[cur][c] == 0) return;
            cur = nxt[cur][c];
            mark[cur] = true;
        }
    }

    static int solve(int cur) {
        int sum = chk[cur] ? 1 : 0;
        for (int i = 0; i < 128; i++) {
            if (nxt[cur][i] == 0) continue;

            if (mark[nxt[cur][i]]) {
                sum += solve(nxt[cur][i]);
            } else {
                sum++;
            }
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());
        while (t-- > 0) {
            init();

            int n = Integer.parseInt(br.readLine());
            while (n-- > 0) {
                insert(br.readLine());
            }

            n = Integer.parseInt(br.readLine());
            if (n == 0) {
                sb.append("1\n");  // rm * 사용
                continue;
            }
            while (n-- > 0) {
                check(br.readLine());
            }

            sb.append(solve(ROOT)).append("\n");
        }

        System.out.println(sb);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 1000 * 20;
const int ROOT = 0;
int unused;
int nxt[MX][128];
bool chk[MX];
int cnt[MX];    // 해당 노드의 자손 노드(해당 노드 포함) 중 지워야 하는 파일의 수
bool mark[MX];  // 지우면 안되는 파일의 접두어에 해당하는 노드들 체크

void init() {
    unused = ROOT + 1;
    memset(nxt, 0, sizeof(nxt));
    memset(chk, 0, sizeof(chk));
    memset(cnt, 0, sizeof(cnt));
    memset(mark, 0, sizeof(mark));
}

void insert(string& s) {
    int cur = ROOT;
    for (char c : s) {
        if (nxt[cur][c] == 0) nxt[cur][c] = unused++;
        cur = nxt[cur][c];
        cnt[cur]++;
    }
    chk[cur] = true;
}

void check(string& s) {
    int cur = ROOT;
    for (char c : s) {
        if (nxt[cur][c] == 0) return;
        cur = nxt[cur][c];
        mark[cur] = true;
    }
}

int solve(int cur) {
    int sum = chk[cur];
    for (int i = 0; i < 128; i++) {
        if (nxt[cur][i] == 0) continue;

        if (mark[nxt[cur][i]]) {
            sum += solve(nxt[cur][i]);
        } else {
            sum++;
        }
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        init();
        int n;

        cin >> n;
        while (n--) {
            string s;
            cin >> s;
            insert(s);
        }

        cin >> n;
        if (n == 0) {
            cout << "1\n";  // rm * 사용
            continue;
        }
        while (n--) {
            string s;
            cin >> s;
            check(s);
        }

        cout << solve(ROOT) << '\n';
    }
}

---