5446 - 용량 부족 (Trie, 정적 풀이)

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

5446번: 용량 부족

Trie만을 위한 마지막 문제가 되지 않을까 싶습니다.

 

Trie 너무 많이 풀었어... 다른거도 풀어야하는데...

 

근데 Trie 문제가 참 재밌어요. Trie라는 개념을 살짝 살짝 바꿔가면 문제들이 풀리는 편이라서 저비용 고효율 느낌??

 

어찌됐건 Trie가 Pro 대비를 위해선 꼭 필요한 개념이니까 튼튼히 다지는 느낌으로 가봅시다.

문제를 읽어보면 결국엔 최소한의 rm 명령 호출 횟 수를 구하는 것입니다. 근데 문제에서 2가지의 입력으로 나눌 수 있습니다. 삭제를 해야하는 파일과 삭제를 해선 안되든 파일, 괜히 아무거나 모두 삭제 해버리면 삭제해선 안되는 파일까지 지워버릴 수 있으니, 완전 큰 일이 나버리는 거죠.

 

예제 입력에서 받은 애들을 한 번 살펴보도록 합시다.

1
11
BAPC.in
BAPC.out
BAPC.tex
filter
filename
filenames
clean
cleanup.IN1
cleanup.IN2
cleanup.out
problem.tex
5
BAPC
files
cleanup
cleanup.IN
cleaning

삭제해선 안되는 파일 중에 BAPC가 존재합니다. 따라서 B*, BA*, BAP*, BAPC*의 명령어를 수행해서는 안되며 BAPC(아무거나)*를 수행해야합니다.

 

cleanup을 볼까요? cleanup이 존재하기에 c*, cl*, cle*, clea*, clean*, cleanu*, cleanup*을 수행해서는 안됩니다.

 

점점 여기에 Trie를 끼얹을 수 있는 방법이 떠오르기 시작합니다.

 

우선 삭제해야 하는 파일을 입력받아 Trie 자료구조에 넣은 후, 삭제해서는 안되는 파일을 Trie에 끼얹어서 Marking을 하면 됩니다. Marking된 문자 뒤엔 *을 붙혀선 안되겠죠?

BAPC에 마킹을 했기 때문에 .에서 삭제를 수행하면 됩니다

여기까지 했으면 거의 다 했습니다. 전체 삭제를 수행 부분을 기억해서 다음 입력에서 반복되는 결과가 나오지 않도록 처리를 하면 될 것이며 (BAPC.in에서 삭제를 했으면, BAPC.out에서는 삭제할 필요가 없으니 걸러야 합니다)

 

또한, Marking을 확인하는 과정에서 삭제해야하는 파일이 나오면 처리를 해줘야합니다. (삭제해야하는 파일 clean은 삭제해서는 안되는 파일 cleanup에 포함되니 이를 처리해야 합니다. 다만, 저는 endOfWord를 사용하지 않았고, 그냥 함수 처리에서 걸러지지 않으면 횟수를 증가시켰습니다)

 

여기까지하면 아마 문제를 풀 수 있을겁니다.

 

...

 

머야

음..

 

왤까요..

 

알고보니 엣지 케이스를 처리를 하지 않아서 발생한 불상사였습니다.

 

흑흑 ㅠㅠ

 

만약 삭제해서는 안되는 파일이 없으면 어떻게 될까요? 그냥 '*'만 실행하면 되겠죠?

 

즉, 1을 출력하면 되는데 저는 이걸 안했습니다. 바보 같이

 

#include <stdio.h>

int trie[20000][80];
int check[20000];

int T, N1, N2, adr, num, result;
char input[30];
char rmList[1000][30];

void initEvery() {
	for (int i = 0; i < 20000; ++i) {
		check[i] = 0;
		for (int j = 0; j < 80; ++j) {
			trie[i][j] = 0;
		}
	}
	adr = 0;
}

void insert(char* word) {
	int idx = 0, cur = 0;
	while (word[idx] != '\0') {
		num = (int)word[idx] - 46;
		if (!trie[cur][num]) trie[cur][num] = ++adr;
		cur = trie[cur][num];
		++idx;
	}
}

void checking(char* word) {
	int idx = 0, cur = 0;
	while (word[idx] != '\0') {
		num = (int)word[idx] - 46;
		if (trie[cur][num]) {
			check[trie[cur][num]] = 1;
			cur = trie[cur][num];
		}
		else break;
		idx++;
	}
}

void rm(char* word) {
	int idx = 0, cur = 0;
	while (word[idx] != '\0') {
		num = (int)word[idx] - 46;
		if (check[trie[cur][num]] != -1 && check[trie[cur][num]] != 0) cur = trie[cur][num];
		else if (check[trie[cur][num]] == -1) return;
		else {
			++result;
			check[trie[cur][num]] = -1;
			return;
		}
		++idx;
	}
	++result;
}

int main(void) {
	scanf("%d", &T);
	for (int t = 0; t < T; ++t) {
		result = 0;
		initEvery();
		scanf("%d", &N1);
		for (int n1 = 0; n1 < N1; ++n1) {
			scanf("%s", rmList[n1]);
			insert(rmList[n1]);
		}
		scanf("%d", &N2);
		for (int n2 = 0; n2 < N2; ++n2) {
			scanf("%s", input);
			checking(input);
		}
		for (int n1 = 0; n1 < N1; ++n1) {
			rm(rmList[n1]);
		}
		if (N2 == 0) printf("1\n");
		else printf("%d\n", result);
	}
}

쨘

---

제가 SSAFY에 있었을 때, 백준 선생님이 와서 특강한 적이 있었는데, 문제 제출하기 전에 엣지케이스가 가장 빈번히 일어나는 부분이라며 항상 최소값, 최댓값을 넣어보고 제출하라 했습니다.

 

항상 가르침을 되새기며 삽시다.

엣지케이스를 잘 챙겨요 우리

---

이상 5446 - 용량 부족 (Trie)였습니다. ^_^