반응형
단어를 저장하기 위해 해시 테이블을 사용한다.
회사에 있는 사람에서는 해시 테이블을 이용해 단어를 저장하고, 정렬하였다.
마찬가지로 외워야할 단어를 저장하고, count한 다음에 정렬해도 된다.
하지만, 여기에서는 우선순위 큐를 갱신하는 방법으로 문제를 풀어보겠다.
먼저 위에서 요구하는 우선순위를 보자.
- 자주 나오는 단어일수록 앞에 배치한다.
- 해당 단어의 길이가 길수록 앞에 배치한다.
- 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다
위의 우선순위에서 단어를 입력받을 때, heap에서 해당 단어의 횟수를 증가시킬 필요가 있다.
우선순위 큐를 이용하여 단어의 수를 update해보자.
단어를 저장하고, 저장된 단어의 있는지 체크하기 위한 HASH_TABLE과 메모리 풀을 위한 POOL을 선언한다.
#define MAX_TABLE (200009)
typedef struct st1
{
int id;
char word[11];
struct st1 *next;
}HASH;
HASH HASH_TABLE[MAX_TABLE];
HASH POOL[MAX];
int pcnt;
HEAP은 아래처럼 구성된다.
자주나오는 단어, 단어의 길이, 그리고 HASH_TABLE의 word를 가르킬 포인터, 그리고 들어온 순서(id)가 필요하다.
typedef struct st2
{
int count;
int length;
char* word;
int id;
}HEAP;
HEAP heap[MAX];
int heapIdx[MAX]; /* id가 heap의 어느 위치에 있는지 저장할 배열 */
int hn;
그 외 구현해야할 string 함수와 hash코드는 아래를 참고한다.
int mystrlen(char * str)
{
int len = 0;
while (*str++) len++;
return len;
}
void mystrcpy(char *a, const char *b)
{
while (*a++ = *b++);
}
int mystrcmp(const char *a, const char *b)
{
while (*a && *a == *b) ++a, ++b;
return *a - *b;
}
ull hash(const char *str)
{
ull hash = 5381;
int c;
while (c = *str++)
{
hash = (((hash << 5) + hash) + c) % MAX_TABLE;
}
return hash % MAX_TABLE;
}문제의 조건에서 단어의 길이가 M보다 작은 경우는 저장할 필요 없으므로 continue로 처리한다.
id는 우선순위 큐에 들어간 순서이다. 새로운 단어가 나올 때마다 id를 1 증가 시킨다.
새로 들어온 id인지 아닌지 check하기 위해 id는 1부터 시작한다.
int main(void)
{
int id;
char str[11];
scanf("%d %d", &N, &M);
id = 1;
for (int i = 0; i < N; i++)
{
scanf("%s", str);
int length = mystrlen(str);
if (length < M) continue;
...
}
...
}
checkExist는 단어와 hash값을 보고 등록된 단어인지 체크한다.
단어가 많으면 많을수록 충돌이 발생할 수 있기 때문에,
HASH_TABLE[h]을 모두 탐색해서 id가 있다면 해당 id를 return하고 없다면 0을 return 한다.
int checkExist(char* word, ull h)
{
HASH *nd = HASH_TABLE[h].next;
while (nd)
{
if (!mystrcmp(nd->word, word)) return nd->id;
nd = nd->next;
}
return 0;
}
checkId가 있는 경우는 update로 checkId를 넘겨줘서 heap에서 직접 count를 증가시킨다.
이때, 아래로 내려가는 경우는 불필요하다.
count는 증가하기만 하기 때문에, update할 node의 우선순위가 낮아지는 경우는 없다.
(당연히 코드를 추가해도 PASS한다.)
void update(HEAP* heap, int& hn, int id, int* heapIdx)
{
HEAP tmp;
int updatehn = heapIdx[id];
heap[updatehn].count++; /* 외워야 할 단어의 개수 추가 */
for (int i = updatehn; i > 1; i /= 2)
{
if (isPriority(heap[i / 2], heap[i])) break;
tmp = heap[i];
heap[i] = heap[i / 2];
heap[i / 2] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i / 2].id] = i / 2;
}
/* 아래로 내려가는 경우는 불필요 */
}
int main(void)
{
...
id = 1;
for (int i = 0; i < N; i++)
{
...
if (length < M) continue;
ull h = hash(str);
int checkId = checkExist(str, h);
/* id가 있으면 update */
if (checkId) update(heap, hn, checkId, heapIdx);
else /* 없다면 추가 */
{
...
}
}
}
checkId가 없는 경우라면 기존의 방식대로 HASH_TABLE에 메모리 풀을 이용하여 node를 연결한다.
heap에 push할 때 최초의 count가 1이므로 1로 넣어주면 된다.
word는 mystrcpy를 이용해도 되지만, 성능을 위해 pointer로 가르키기만 하자.
checkId가 0이란 것은 새로 들어온 단어이므로 id를 저장한 후에는 ++로 새로운 id로 갱신해야 한다.
int main(void)
{
...
id = 1;
for (int i = 0; i < N; i++)
{
...
/* id가 있으면 update */
if (checkId) update(heap, hn, checkId, heapIdx);
else /* 없다면 추가 */
{
HASH *nd = &POOL[pcnt++];
nd->id = id; /* id 는 1부터 시작 */
mystrcpy(nd->word, str);
nd->next = HASH_TABLE[h].next;
HASH_TABLE[h].next = nd; /* name에 해당하는 key에 연결 */
HEAP dic = { 0 };
dic.count = 1; /* 최초 count는 1 */
dic.length = length;
dic.word = nd->word; /* pointer로 HASH의 word를 가르키기만 한다. */
dic.id = id++;
push(heap, hn, dic, heapIdx);
}
}
}
마지막으로 hn이 0이 될 때까지 pop하면 정렬이 된다.
int main(void)
{
...
for (int i = 0; i < N; i++)
{
/* 입력 및 갱신 */
}
while (hn)
{
HEAP dic = pop(heap, hn, heapIdx);
printf("%s\n", dic.word);
}
return 0;
}
pop과 push는 전체 코드를 참고하자.
우선순위 비교 함수는 위에서 요구한대로 구현하면 된다.
pop에서는 최악의 값으로 count와 length에 -1을 주었다.
참고로 word를 최악의 값으로 변경해서는 안된다. 현재 pointer로 HASH_TABLE을 가르키고 있기 때문이다.
그리고 id에 대한 우선순위도 없으므로 pop에서 수정하지 않는다.
#include <stdio.h>
#define MAX (100000 + 1000)
#define MAX_TABLE (200009)
typedef unsigned long long int ull;
int N, M;
typedef struct st1
{
int id;
char word[11];
struct st1 *next;
}HASH;
HASH HASH_TABLE[MAX_TABLE];
HASH POOL[MAX];
int pcnt;
typedef struct st2
{
int count;
int length;
char* word;
int id;
}HEAP;
HEAP heap[MAX];
int heapIdx[MAX]; /* id가 heap의 어느 위치에 있는지 저장할 배열 */
int hn;
int mystrlen(char * str)
{
int len = 0;
while (*str++) len++;
return len;
}
void mystrcpy(char *a, const char *b)
{
while (*a++ = *b++);
}
int mystrcmp(const char *a, const char *b)
{
while (*a && *a == *b) ++a, ++b;
return *a - *b;
}
ull hash(const char *str)
{
ull hash = 5381;
int c;
while (c = *str++)
{
hash = (((hash << 5) + hash) + c) % MAX_TABLE;
}
return hash % MAX_TABLE;
}
int isPriority(HEAP a, HEAP b)
{
if (a.count > b.count) return 1;
else if (a.count == b.count && a.length > b.length) return 1;
else if (a.count == b.count && a.length == b.length && mystrcmp(a.word, b.word) < 0) return 1;
return 0;
}
HEAP pop(HEAP* heap, int& hn, int* heapIdx)
{
register HEAP tmp, ret;
ret = heap[1];
heap[1] = heap[hn];
heap[hn].count = -1;
heap[hn--].length = -1;
/* 마지막에 한꺼번에 pop을 하므로 heap[hn].word를 최악으로 수정할 필요는 없다. */
/* heap[hn].id 에 대한 우선순위가 없으므로 수정 불필요*/
for (register int i = 1; i * 2 <= hn;)
{
if (isPriority(heap[i], heap[i * 2]) && isPriority(heap[i], heap[i * 2 + 1])) break;
else if (isPriority(heap[i * 2], heap[i * 2 + 1]))
{
tmp = heap[i * 2];
heap[i * 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2].id] = i * 2;
i = i * 2;
}
else
{
tmp = heap[i * 2 + 1];
heap[i * 2 + 1] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i * 2 + 1].id] = i * 2 + 1;
i = i * 2 + 1;
}
}
return ret;
}
void push(HEAP* heap, int& hn, HEAP x, int* heapIdx)
{
register HEAP tmp;
heap[++hn] = x;
heapIdx[x.id] = hn;
for (register int i = hn; i > 1; i /= 2)
{
if (isPriority(heap[i / 2], heap[i])) break;
tmp = heap[i / 2];
heap[i / 2] = heap[i];
heap[i] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i / 2].id] = i / 2;
}
}
void update(HEAP* heap, int& hn, int id, int* heapIdx)
{
HEAP tmp;
int updatehn = heapIdx[id];
heap[updatehn].count++; /* 외워야 할 단어의 개수 추가 */
for (int i = updatehn; i > 1; i /= 2)
{
if (isPriority(heap[i / 2], heap[i])) break;
tmp = heap[i];
heap[i] = heap[i / 2];
heap[i / 2] = tmp;
heapIdx[heap[i].id] = i;
heapIdx[heap[i / 2].id] = i / 2;
}
/* 아래로 내려가는 경우는 불필요 */
}
int checkExist(char* word, ull h)
{
HASH *nd = HASH_TABLE[h].next;
while (nd)
{
if (!mystrcmp(nd->word, word)) return nd->id;
nd = nd->next;
}
return 0;
}
int main(void)
{
int id;
char str[11];
scanf("%d %d", &N, &M);
id = 1;
for (int i = 0; i < N; i++)
{
scanf("%s", str);
int length = mystrlen(str);
if (length < M) continue;
ull h = hash(str);
int checkId = checkExist(str, h);
if (checkId) update(heap, hn, checkId, heapIdx);
else
{
HASH *nd = &POOL[pcnt++];
nd->id = id; /* id 는 1부터 시작 */
mystrcpy(nd->word, str);
nd->next = HASH_TABLE[h].next;
HASH_TABLE[h].next = nd; /* name에 해당하는 key에 연결 */
HEAP dic = { 0 };
dic.count = 1; /* 최초 count는 1 */
dic.length = length;
dic.word = nd->word; /* pointer로 HASH의 word를 가르키기만 한다. */
dic.id = id++;
push(heap, hn, dic, heapIdx);
}
}
while (hn)
{
HEAP dic = pop(heap, hn, heapIdx);
printf("%s\n", dic.word);
}
return 0;
}반응형
'알고리즘 > [PRO] 삼성 SW 역량 테스트 B형' 카테고리의 다른 글
| 삼성 C형 샘플 문제 : 블록 부품 맞추기 (0) | 2021.03.30 |
|---|---|
| BOJ 7662 : 이중 우선순위 큐 (1) | 2021.03.24 |
| BOJ 18139 : Rush Hour Puzzle (해시, 2차원 배열 탐색) (2) | 2021.03.18 |
| Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 (2) : 최적화 (0) | 2021.03.13 |
| Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 (1) | 2021.03.13 |
댓글