[백준 5052] 전화번호 목록

문제 링크 => 5052번: 전화번호 목록 (acmicpc.net)

5052번: 전화번호 목록

 

Trie 자료구조를 이용한 문제이다.

 

사실 Sorting 을 이용하면 난이도가 급격하게 낮아지지만 삼성 하계 sw 때 배웠던 자료구조 Trie 를

이용해서 풀었다.

 

문제 자체의 흐름은 파악했으나 실수한 점이 있다.

 

Input을 하나하나 읽은 동시에 바로 check 했다는 점에 있다.

 

예시를 들어보자.

 

12345, 123 순으로 들어왔다고 가정한다면

 

(1) 12345 => 끝부분 5에 mark 표시

 

(2) 123 => 겹치는 prefix가 없으므로 끝부분 3에 mark 표시

 

와 같은 일이 벌어진다.

 

즉, 123, 12345 와 같은 순으로 들어온다면 참 다행이겠지만 그렇지 않다는 것이다.

 

따라서 모든 Input들에 대한 mark 표시 후에 다시 for loop 을 돌려서 mark를 check하는 방법으로 

구현해야 한다.

 

위와 같은 Input case가 존재했다면 금방 해결했을 거 같은데 아쉽다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

bool Result;

struct Phone* myAlloc();

struct Phone {
	Phone *next[10];
	int mark;
	void addPhone(const char* dial) {
		if (*dial != '\0') {
			if (next[*dial - '0'] == nullptr)
				next[*dial - '0'] = myAlloc();
			next[*dial - '0']->addPhone(dial + 1);
		}
		else {
			mark = 1;
		}
	}
	bool check(const char* dial) {
		if (*dial == '\0')
			return true;
		if (mark) // 이부분이 핵심
			return false;
		return next[*dial - '0']->check(dial + 1);
	}
	void clear() {
		mark = 0;
		for (int i = 0; i < 10; i++)
			next[i] = nullptr;
	}
};

Phone dummy[100001];
int dum_cnt;

Phone* myAlloc() { // 삼성에서 배웠던 Memory Pool 기법 활용
	dummy[dum_cnt].clear();
	return &dummy[dum_cnt++];
}

const char* test() {
	int i, n, op;
	Phone* root;
	char dial[10000][11];

	scanf("%d", &n);
	dum_cnt = 0;
	root = myAlloc();
	Result = true;
	for (i = 0; i < n; i++) {
		scanf("%s", dial[i]);
		root->addPhone(dial[i]);
	}
	for (i = 0; i < n; i++)
		if (!(Result = root->check(dial[i])))
			return "NO";
	return "YES";
}

int main(void)
{
	int t;
	scanf("%d", &t);
	while (t--)
		printf("%s\n", test());

	return 0;
}