5052 - 전화번호 목록

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

5052번: 전화번호 목록

문자열 알고리즘, 자료구조엔 투 톱이 있습니다. (주관적인 생각입니다)

 

해시(hash)와 트라이(Trie)가 바로 그 것인데요.

 

해시는 여러분들이 흔히 사용하는 Python의 dictionary라고 생각하면 됩니다. (제가 파이썬 유저라 ㅎㅎ)

 

그렇다면 트라이는 무엇일까요?

 

트라이 자료구조는 문자열 검색에서 많이 사용되는 자료구조입니다. (알고리즘? 자료구조? 어떻게 불러야 할 지 애매하기에 자료구조라고 명하겠습니다)

 

제가 알아본 바로는 저희 자동 검색기능 있잖아요? '네'까지만 쳐도 '네이버'가 나오는 검색창, 그걸 트라이로 구현할 수 있다고 하네요.

 

이처럼 실생활에서도 많이 쓰는 트라이기에 트라이의 가장 기본 문제인 전화번호 목록을 풀어봤습니다.

 

트라이라 함은 한 글자씩 노드를 타고내려 가면서 그 다음 글자가 있는지를 확인하는 자료구조입니다. 또한, 단어의 끝에 endOfWord와 같은 boolean 계수를 추가하면서 그 단어가 끝인지 아닌지를 파악한다면 '119', '1191'과 같은 중복되는 숫자가 있는 경우에도 저장을 할 수 있습니다.

 

저 역시 위와 같은 방법으로 풀었습니다. 노드에는 endOfWord로 글자가 끝나는 지점을 표시하고 0 ~ 9까지의 숫자 배열을 두어서 다음 노드로 넘어갈 수 있는 다리를 놓았습니다. 만약 word 배열의 값에 주소값이 있다면 그 인덱스 번호는 다음 노드로 넘어갈 수 있는 것이지요. 마치 위의 트리 그림과 유사하게요.

 

이처럼 문제를 해결한다면 누구나 쉽게 풀 수 있는 문제라 생각합니다.

 

하지만, 진정한 어려움은 트라이를 다른데 접목시키는 거겠죠..?

 

흑흑

#include <stdio.h>
#include <malloc.h>

typedef struct _node {
	int endOfWord;
	struct _node* word[10];
} Node;

Node* makeNode(void) {
	Node* temp = (Node*)malloc(sizeof(Node));
	temp->endOfWord = 0;
	for (int i = 0; i < 10; i++) temp->word[i] = 0;
	return temp;
}

int T, N;
char number[11];
Node* trie;

int triePush(const char* number) {
	int idx = 0, num, boolean = 0;
	Node* root = trie;
	Node* temp;
	while (number[idx] != '\0' && !root->endOfWord) {
		num = (int)number[idx] - '0';
		if (!root->word[num]) {
			temp = makeNode();
			root->word[num] = temp;
			boolean = 1;
		}
		root = root->word[num];
		idx++;
	}
	if (!boolean) return 0;
	root->endOfWord = 1;
	return 1;
}

int main(void) {
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		int result = 1;
		trie = makeNode();
		scanf("%d", &N);
		for (int n = 0; n < N; n++) {
			scanf("%s", number);
			if (triePush(number)) continue;
			else result = 0;
		}
		if (result) printf("YES\n");
		else printf("NO\n");
	}
}

---

이상 5052 - 전화번호 목록였습니다. ^_^