14. 1133 : Uniqueness

원본 출처 : http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=413&sca=50&sfl=wr_subject&stx=UNIQUENESS&sop=and

JUNGOL | Uniqueness > 문제은행

문제 풀이 : 

#include <stdio.h>
#include <malloc.h>
#define MAX (10001)
#define STEP 1
//구조체 설계
typedef struct _node {
    int index;
    struct _node *next;
}NODE;
//헤시테이블.. 이름과 hash_value값을 가지고 있어야한다..
typedef struct _head {
    int cnt;
    char str[21];
    struct _node *next;
}HEAD;
HEAD head_table[MAX];   //신규 문자열의 해더 테이블
int head_pos[MAX];      //해더의 위치를 순서대로 기록
int head_cnt = 0;       //해더 개수
int N;
int str_cmp(char* p, char* q)
{
    int i;
    for (i = 0; p[i] && q[i] && p[i] == q[i]; i++);
    return p[i] - q[i];
}
int str_cpy(char* p, char* q)
{
    //while (*p++ = *q++);
    int i;
    for (i = 0; p[i] = q[i]; i++);
    return i; // return 필요 없긴 함.
}
int get_hash(char *p) {//djb2 방법
    int hash = 5381;
    int i;
    for (i = 0; p[i]; i++) {
      hash = (hash * 33 + p[i]) % MAX;    //hash <<5 + hash
    }
    return hash;
}
int get_head_key(char *p) {
    int i, key = get_hash(p);
    //해당 해시키로 해시테이블(헤더)에 배정(충돌이면 빈자리에 배정)
    //충돌이면 빈자리 배정
    for (i = 0; i < MAX; i++) {
        if (head_table[key].cnt == 0 || !str_cmp(head_table[key].str, p)) return key;
        key = (key + STEP) % MAX;   //충돌이면 빈자리에 배정
        //break;
    }
    return key;
}
void insert_node(HEAD *p, int idx) {
    NODE* new = (NODE*)malloc(sizeof(NODE));
    new->index = idx;
    new->next = p->next;
    p->next = new;
}
int solve(void) {
    int i, uniq = 1, key;
    char str[21];
    for (i = 1; i <= N; i++) {
        scanf("%s", str);
        //printf("scanf: %s\n", str);
        key = get_head_key(str);
        //해당 문자열의 해시키값에 해당 헤더가 없으면 첫문자열이므로 헤더에 저장하고 위치 기록
        if (head_table[key].cnt == 0) {
            //head_table[key].cnt++;
            str_cpy(head_table[key].str, str);
            head_pos[head_cnt++] = key;
        }
        head_table[key].cnt++;
        if (uniq && head_table[key].cnt > 1) uniq = 0;   //유니크 체크
        //해당 문자열의 위치값을 링크
        insert_node(&head_table[key], i);   //현재 위치 값을 현해더에 링크 연결
    }
    return uniq;
}
void print_node(NODE *p) {
    //재귀적으로 역순 인쇄
    if (p == 0) return;
    print_node(p->next);
    printf(" %d", p->index);
}
void print_all(void) {
    //2개 이상만 출력
    int i, key;
    for (i = 0; i < head_cnt; i++) {
        key = head_pos[i];
        if (head_table[key].cnt > 1) {
            printf("%s", head_table[key].str);
            print_node(head_table[key].next);
            printf("\n");
        }
    }
}
 
int main() {
    scanf("%d", &N);    //10
    if (solve())printf("unique\n");
    else print_all();
    return 0;
}