12791 - Starman

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

12791번: Starman

문자열 알고리즘의 투 톱 중 트라이는 앞선 전화번호 목록에서 풀어보았습니다.

 

https://ggodong.tistory.com/160

5052 - 전화번호 목록

이젠 투 톱 중 다른 한 알고리즘인 해시를 확인해 볼 차례입니다.

 

해시.. 이 놈은 참 간단하면서도 어려운 알고리즘이라 생각합니다.

 

Python에서는 그냥 뿅하면 뿅 나오는 애로 배웠는데, 이를 c로 직접 구현하려니... 흑흑

 

해시는 아시다시피 key 값을 넣으면 그에 상응하는 value가 나오는 자료구조 입니다.

 

마치 열쇠와 자물쇠 관계와도 같죠.

 

허나... 현대의 해시 알고리즘은 완벽하지 않아서 가끔가다 충돌이라는 개념이 나오게 됩니다.

 

다른 열쇠로 같은 자물쇠를 열 수 있는 것과 유사합니다.

 

우리는 SW 개발자, SW 지식인이기 때문에 이러한 상황에서 해결책을 찾아야 합니다. 그래서 나온 것이 Linked List라는 자료구조로 해결하는 방법입니다.

 

사실 이번 문제는 범위가 워어어어어낙 작아서 그냥 배열로 두고 풀어도 됩니다.

 

하지만, 해시도 연습할 겸, 포인터도 연습할 겸해서 이상하게? 풀어보았습니다.

 

아래의 코드를 보시면, 우선 node가 있습니다. 이 노드는 next라는 값을 가지고 있으며 next는 주소값을 가리키고 있습니다. 즉, Linked List의 한 노드가 되는 것입니다.

 

그 밑엔 dic이라는 구조체가 있는데 이 구조체는 head와 cnt를 가지고 있습니다. cnt는 그 위치에서 가지고 있는 데이터 갯수를 뜻하고 head는 뭘까요?

 

head는 Linked List 노드를 가리키고 있습니다.

 

즉, 이렇게 하므로써 아래와 같은 해시가 만들어지는 것입니다.

 

이해되죠 ㅎㅅㅎ?

 

나머지 부분은 코드를 보시면 이해가 되실거라 생각합니다.

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

typedef struct _node {
	char name[100];
	struct _node* next;
} Node;

typedef struct _dic {
	int cnt;
	struct _node* head;
} Dic;

Dic dict[50];
Node* tmp,* cur;
int Q, S, E, re;

void initDic() {
	for (int i = 0; i < 30; i++) {
		dict[i].cnt = 0;
		dict[i].head = NULL;
	}
}

Node* newNode() {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	return newNode;
}

void my_strcpy(char* str1, const char* str2) {
	int idx = 0;
	while (str2[idx] != '\0') {
		str1[idx] = str2[idx];
		idx++;
	}
	str1[idx] = '\0';
}

void insert(int year, const char* name) {
	int idx = year - 1967;
	tmp = newNode();
	my_strcpy(tmp->name, name);
	if (!dict[idx].cnt) {
		dict[idx].head = tmp;
	}
	else {
		cur = dict[idx].head;
		while (cur->next) {
			cur = cur->next;
		}
		cur->next = tmp;
	}
	dict[idx].cnt++;
}

void findResult(int year) {
	int idx = year - 1967;
	if (dict[idx].cnt) re += dict[idx].cnt;
}

void find(int year) {
	int idx = year - 1967;
	if (dict[idx].cnt) {
		cur = dict[idx].head;
		while (cur) {
			printf("%d %s\n", year, cur->name);
			cur = cur->next;
		}
	}
}

int main(void) {
	initDic();

	insert(1967, "DavidBowie");
	insert(1969, "SpaceOddity");
	insert(1970, "TheManWhoSoldTheWorld");
	insert(1971, "HunkyDory");
	insert(1972, "TheRiseAndFallOfZiggyStardustAndTheSpidersFromMars");
	insert(1973, "AladdinSane");
	insert(1973, "PinUps");
	insert(1974, "DiamondDogs");
	insert(1975, "YoungAmericans");
	insert(1976, "StationToStation");
	insert(1977, "Low");
	insert(1977, "Heroes");
	insert(1979, "Lodger");
	insert(1980, "ScaryMonstersAndSuperCreeps");
	insert(1983, "LetsDance");
	insert(1984, "Tonight");
	insert(1987, "NeverLetMeDown");
	insert(1993, "BlackTieWhiteNoise");
	insert(1995, "1.Outside");
	insert(1997, "Earthling");
	insert(1999, "Hours");
	insert(2002, "Heathen");
	insert(2003, "Reality");
	insert(2013, "TheNextDay");
	insert(2016, "BlackStar");

	scanf("%d", &Q);
	for (int q = 0; q < Q; q++) {
		re = 0;
		scanf("%d %d", &S, &E);
		for (int s = S; s <= E; s++) {
			if (1967 <= s && s <= 2016) {
				findResult(s);
			}
		}
		printf("%d\n", re);
		for (int s = S; s <= E; s++) {
			if (1967 <= s && s <= 2016) {
				find(s);
			}
		}
	}
}

---

이상 12791 - Starman였습니다. ^_^