[Jungol] 정올 1133 UNIQUENESS2

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=413&sca=99

Approach

- 중복없이 이름을 저장하기 위해서 Hash 구현 (+ Chaining 기법)

- Hash에 자료저장시 문자열 주소와 고유 ID를 저장합니다.

- 문자열의 등장하는 순서를 별도의 연결리스트로 관리합니다.

 

① Hash에 등록된 이름이 없다면 Hash에 새롭게 추가합니다. (문자열 비교)

    + 새로운 ID를 부여합니다. (ID는 1번부터 순차적으로 부여)

 

② 기존에 이름의 ID 혹은 새롭게 부여된 ID를 이용해서 나타난 순서를 

    리스트에 추가합니다. (head 다음 지점에 추가합니다.)

 

③ ID가 N번째까지 부여된 경우는 입력받은 이름에서 중복이 없는 것을 의미하므로 "unique" 출력

    그렇지 않은 경우 중복된 이름이 발생하는 경우(리스트의 크기가 ≥ 2) 등장한 순서 출력

    리스트에는 최근에 등장한 순서가 앞쪽에 있는것에 유의

    

 재귀탐색을 이용한 역추적 방식

 

▶ [해시] Hash란?

[해시] Hash란?

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int MAXN = 1e5;
const int MAX_STR = 20;
const int SIZE = 1 << 16;
const int MOD = (SIZE - 1);
 
int N, newID, id;
char name[MAXN + 2][MAX_STR + 2];
 
int strcmp(const char* s, const char* t) {
    while (*s && *s == *t) ++s, ++t;
    return *s - *t;
}
 
int djb2(char* s) {
    int hash = 5381;
    for (; *s; ++s)
        hash = hash * 33 + *s;
    return hash & MOD;
}
 
struct HashNode {
    char* nameAddr; // 이름 주소
    int id;
    HashNode* next;
 
    HashNode* alloc(char* nameAddr, int id, HashNode* next) {
        this->next = next;
        this->id = id;
        this->nameAddr = nameAddr;
        return this;
    }
}hashBuf[MAXN + 10], hashTable[SIZE];
int hash_bcnt, h_idx;
 
HashNode* probing(int hidx, char* target) {
    HashNode* p = hashTable + hidx;
    for (; p->next; p = p->next) {
        if (strcmp(p->next->nameAddr, target) == 0) return p->next;
    }
    return NULL;
}
 
struct StrNode {
    int idx; // 문자열이 들어온 순서 번호
    StrNode* next;
 
    StrNode* alloc(int idx, StrNode* next) {
        this->next = next;
        this->idx = idx;
        return this;
    }
}strBuf[MAXN + 10], head[MAXN + 10];
// 문자열이 중복된 개수 (head[i]가 가르키는 리스트 크기)
int headCnt[MAXN + 10];
int str_bcnt;
 
void PrtNode(StrNode* p) {
    if (p == NULL) return;
    PrtNode(p->next);
    printf(" %d", p->idx);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
 
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        scanf("%s", name[i]);
 
        // Hash Index 구하기
        int h_idx = djb2(name[i]);
 
        // 기존 Hash Table 탐색
        HashNode* p = probing(h_idx, name[i]);
 
        // Hash Table에 없는 이름인 경우
        if (p == NULL) {
            // Hash Table 등록
            hashTable[h_idx].next = hashBuf[hash_bcnt++].alloc(name[i], ++newID, hashTable[h_idx].next);
            id = newID;
        }
        else id = p->id;
 
        // 들어온 순서를 리스트에 추가
        head[id].next = strBuf[str_bcnt++].alloc(i, head[id].next);
        headCnt[id]++;
    }
 
    // 이름이 중복이 없어서 newID가 N인 경우
    if (newID == N) {
        printf("unique\n");
        return 0;
    }
 
    for (int i = 1; i <= newID; i++) {
        // 중복이 없는 이름인 경우
        if (headCnt[i] < 2) continue;
 
        // 중복된 이름 출력(해당 순서(idx)에 입력된 이름을 출력)
        // 즉, 중복된 해당 이름이 마지막으로 입력된 경우에 해당
        printf("%s", name[head[i].next->idx]);
 
        // 먼저 입력된 순서가 리스트 뒤쪽에 있으므로 역추적
        PrtNode(head[i].next);
        printf("\n");
    }
}