c언어 5670번 휴대폰 자판 (백준)

#include <stdio.h>
#include <stdlib.h>

int ans = 0; //각 테스트 케이스마다 자판을 몇 번 누르는지를 담는 변수
typedef struct Trie { //트라이를 구성할 구조체
	struct Trie *next, *child; //각 노드마다 자신의 옆과, 자신의 자식을 가리킴
	char data; //문자
	int cnt; //몇 개? (중복)
}Trie;

Trie * make(Trie * root, char c) { //트라이 만들기
	for(Trie*p=root->child;p!=NULL;p=p->next) { //기존에 있는 것인지 확인하기
		if(c == p->data) { //비교는 문자를 이용하여
			p->cnt++; //있다면 중복이므로 1을 증가
			return p; //이 노드의 주소값을 반환
		}
	}
	
	Trie * node = malloc(sizeof(Trie)); //새로운 노드 동적할당
	node->child = NULL; //초기화
	node->data = c; //문자
	node->cnt = 1; //1개!
	node->next = root->child; //이 노드의 옆은 부모노드의 원래자식을 가리킵니다 (NULL일 수도 있습니다)
	root->child = node;	//부모노드는 이제 새로 생긴 노드를 자식으로 가리킵니다. (기존의 자식은 새로운 노드의 옆에 있으니 탐색이 가능합니다)
	return node; //이 주소값을 반환
}

void find(Trie * root, int k) { //몇 번 자판을 눌러야 하는지 계산하는 함수
	for(Trie*p=root->child;p!=NULL;p=p->next) { //부모노드에 대한 자식노드들을 탐색
		if(p->cnt < k) ans += p->cnt; //이전 과정보다 값이 작다면, 이는 서로 다른 단어들이 있다는 의미이다 (최소 2개) 이러면 자판을 단어마다 눌러주어야 한다. 이 값을 ans에 누적
		if(p->cnt > 1) find(p, p->cnt); //단어가 2개 이상인 경우, 더 깊이 탐색한다. 1개인 경우 굳이 탐색할 필요가 없다, 더 이상 자판을 누르지 않기 때문이다.
	} return;
}

int main(void) {
	int t; //테스트 케이스
	char s[81]={};
	while(~scanf("%d",&t)) { //scanf는 입력받은 인자의 개수를 return 한다. EOF의 경우 -1을 리턴한다. not (-1) = 0 = false 이다. -1은 11111...111 임을 기억하자
		ans = 0;
		Trie * root = malloc(sizeof(Trie)); //트라이의 루트가 될 것을 동적할당한다.
		root->next = root->child = NULL; //주소를 다루는 값들을 초기화한다. (안하면 어떤 오류가 발생할지 모른다!)
		
		for(int i=0; i<t; i++) { 
			scanf("%s",s); //단어를 입력받는다.
			Trie * tmp = root; 
			for(int j=0; s[j]!=0; j++) { //문자 하나하나 쪼개서 트라이에 집어 넣는다.
				tmp = make(tmp, s[j]);
			}
		}
		
		find(root, t); //탐색
		if(root->child->cnt == t) ans+=t; //위의 탐색 함수는 치명적인 결합이 있다. 자식이 두개 있을 때 작동을 하기 때문에, root의 자식이 1개밖에 없는 경우 (ex hi, he, ho) 3번 눌러야 하는 것을 ans에 반영할수가 없다. 이를 해결하기위해 추가적으로 적어논 코드이다.
		printf("%.2f\n", (float)ans/t); //평균횟수 출력
		free(root); //트라이 root를 동적할당 해제, 사실 다른 구성요소들도 할당하는 것이 맞다...
	}
}

 

풀이 : 트라이

 

1. 트라이 만들기

이것이 위의 코드에서 트라이를 구성하는 노드 입니다.

 

 

이런식으로 구성이 됩니다.

 

트라이를 구성할 때, 문자열을 문자로 쪼갠다음에 구성하게 되며, 이미 같은 나열이 있다면 새로운 노드를 만드는 것이 아니라, 기존 노드에 중복을 의미하는 값만 1 증가시켜줍니다.

 

 

2. 자판의 개수를 탐색하는 법

 

 자식이 2개이상이라면 이것은 눌러야할 알파벳이 다르다는 것을 의미하며, 이때는 단어를 만들기 위해선 다시 한번 전부 자판을 눌러주어야 합니다.

 

ex)

hi

app

ape

 

트라이 루트의 자식은 h, a라는 값을 가집니다. 즉 자판을 눌러주어야 합니다. h의 cnt값 1, a의 cnt값 2 고로 ans의 값은 3이 됩니다.

 

그다음 hi 먼저 보게되면, 이 경우 단어가 1개이므로 더이상 중복되는 단어들이 없기에 바로 완성이 된 상태입니다. 고로 자판을 누를 필요가 없으니 탐색도 할 필요가 없습니다. 이를 일반화 하면

 

cnt값이 1이면, 더이상 입력하지 않아도 된다.

 

app, ape의 경우 두번째 단어는 p 이며, 이 들은 ap 라는 노드가 담당하고 있으며, cnt값은 2 입니다. 그러나 자판을 누를 이유는 없습니다 (문자가 같아 또 누를 필요가 없습니다)   즉 이전단계의 cnt값인 2와 같음을 알 수 있고, 이를 일반화 하면

 

부모 노드의 cnt값과 자식 노드의 cnt값이 같다면 이는 알파벳의 중복을 의미하며, 자판을 누르지 않는다.

 

cnt값이 1이면, 더이상 입력하지 않아도 된다.
부모 노드의 cnt값과 자식 노드의 cnt값이 같다면 이는 알파벳의 중복을 의미하며, 자판을 누르지 않는다.

 

이 두가지 요소를 구현한 것이 바로 위의 find 함수 입니다.

 

3 위 함수의 문제점

위 함수는 자식이 여러개 일 때를 단어의 철자가 다름으로 인식하고 개수를 구하게 됩니다.

그러나 hi, he 처럼 시작부분이 같아버리면 i, e로 달라질때 눌러야 함은 구할 수 있으나, 시작할 때 두번 눌러야 하는 것은 계산할 수 가 없습니다...

 

그래서 맨 처음 부분이 같은 경우를 예외적으로 처리해 주어야 합니다. 그 코드가 바로

if(root->child->cnt == t) ans+=t; 입니다.

 

해석하면 트라이의 루트 노드의 자식이 1개라면 (중복값이 t라면, 처음 문자가 전부 같다는 것을 의미합니다) t만큼ans에 더하라.

 

ex) aa ab ac

root의 자식은 a를 값으로 가진 노드이며 cnt값은 3입니다. t값은 입력 받은 문자열의 개수를 의미하며, 이 t값과 cnt가 같다면 이는 모든 문자열의 처음 문자가 전부 같다는 것을 의미합니다. 다른 말로 root의 자식은 하나의 노드라는 것을 알 수 있습니다.

 

 

이렇게

1. 트라이를 구현하고

2. 단어들의 철자가 달라지는 분기점에서 몇 번 입력하는지의 횟수를 누적시키고

3. 모든 단어의 시작이 같은 경우를 예외적으로 처리하면

 

답을 구할 수 있습니다!!!

 

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