[백준][C++] 5446: 용량 부족

문제 링크: https://www.acmicpc.net/problem/5446

 

지워야 하는 파일 목록이 쭉 들어오고, 그 다음 지우면 안되는 파일의 목록이 쭉 들어옵니다.

이 때 지우고 싶은 파일을 모두 지우는 데 필요한 최소 rm 커맨드 사용 횟수를 구하는 것이 문제입니다.

 

일단 트라이(trie)로 푸는 방법이 있겠습니다. 좀 생각을 해봐야되는데.. 제 알고리즘은 이렇습니다.

• 지울 파일들을 트라이에 넣는다
  • 이때 문자 끝에는 terminal 체크를 해준다
  • 각 문자들마다 removable(지울 수 있음) 체크를 해준다
• 지워야 할 파일들을 트라이에 넣는다
  • 각 문자들마다 removable을 false로 바꿔놓는다
• 마지막으로 dfs를 돌면서 적당히 경우의 수를 센다
  • leaf 노드인 경우 (base case)
    • removable == true인 경우 ++cnt
  • leaf가 아닌 경우
    • 현재 노드가 removable 하면서 자식 노드들이 전부 removable 한 경우
      • ++cnt 하고 이 노드 탐색은 끝냄 (pruning)
    • 현재 노드가 terminal이면서 자식 노드중에 한 개 이상이 removable 하지 않은 경우
      • ++cnt
    • 전부 아니면 자식노드들 dfs 수행

 

조금 뭔가 복잡하게 썼는데;;; 코드로 보시죠

#pragma GCC optimize ("Ofast")

#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

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


int counter;

struct trie_node {
	map<char, trie_node> children;

	bool removable;
	bool terminal;

	trie_node() : removable(true), terminal(false) {}
};

void trie_insert(trie_node& root, const string& s, bool rm) {
	trie_node* curr = &root;

	for (const auto& c : s) {
		if (curr->children.find(c) == curr->children.end())
			curr->children[c] = trie_node();

		if (!rm)
			curr->children[c].removable = false;
		curr = &(curr->children[c]);
	}

	if (rm)
		curr->terminal = true;
}


auto fold = [](int a, const pair<const char, trie_node>& p) { return a + p.second.removable; };

void dfs(const trie_node& root) {
	// leaf node
	if (root.children.empty()) {
		if (root.removable)
			++counter;
		return;
	}

	// check if terminal node or prunable node(*)
	auto folded = accumulate(root.children.begin(), root.children.end(), 0, fold);
	const auto& sz = root.children.size();
	if ((folded == sz && root.removable) || (folded != sz && root.terminal)) {
		++counter;
		
		if (root.removable) {
			return;
		}
	}

	for (const auto& [ch, node] : root.children) {
		dfs(node);
	}
}


int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		trie_node root;
		counter = 0;

		int n;
		string s;

		cin >> n;
		while (n--) {
			cin >> s;
			trie_insert(root, s, true);
		}

		cin >> n;
		while (n--) {
			cin >> s;
			trie_insert(root, s, false);
		}

		dfs(root);
		cout << counter << '\n';
	}

	return 0;
}

map으로 트라이를 만들었습니다. unordered_map으로 하려고 했더니 msvc에서만 되고 다른 컴파일러들은 컴파일이 안되네요. 흐음

맞은 사람 코드를 보니 이분탐색으로 푼 사람도 있네요.