[Jungol] 정올 3142 ID 검사

출처: [Jungol] 정올 3142 ID 검사

Approach

아래 각 구현시, 사용자가 로그인 여부 / 탈퇴 등에 상태를 Hash로 관리하면 된다.

1. 가입 여부

2. 로그인 여부

3. 회원가입처리: 가입 후 자동 로그인 되지 않음

4. 탈퇴 처리

5. 로그인 처리

6. 로그아웃 처리

 

▶ [해시] Hash란?

[해시] Hash란?

 

 

STL Version

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
#include <string>
using namespace std;
set<string> id, act;
int N, cmd;
char str[15];
int main() {
    // freopen("input.txt", "r", stdin);
    int N, cmd, i;
    scanf("%d", &N);
    for (i = 0; i < N; ++i) {
        scanf("%d %s", &cmd, str);
        switch (cmd){
        case 1: printf("%d\n", id.count(str));  break;
        case 2: printf("%d\n", act.count(str)); break;
        case 3: id.insert(str), printf("%d\n", id.size()); break;
        case 4: id.erase(str), act.erase(str);
                printf("%d\n", id.size()); break;
        case 5: if (id.count(str)) act.insert(str);
                printf("%d\n", act.size()); break;
        case 6: act.erase(str);
                printf("%d\n", act.size()); break;
        }
    }
}

---

문자열 Hash 직접 구현

key값으로 문자열 포인터를 login 여부를 저장하는 멤버 변수를 사용

- leading zero가 올 수 있기에 문자열을 37진법 수로 보고 long long 타입의 10진수로 바꾼 값을 key로 처리

  (ex. "01" ≠ "1")

- 삭제를 용이하기 위해서 Hash Table에서 더미노드 사용

  첫번째 원소가 더미 노드 역할로 사용하기 위해 포인터로 선언 X

 

 

- key 값을 숫자로 처리

- 등록 수나 로그인 수를 쉽게 구하기 위해서 regCnt, actCnt를 두었는데,

   Hash Table 값을 변경할 때 데이터 연계에 주의합니다.

   ex) [4] 탈퇴처리 할 때, 등록 수 감소와 함께 로그인 되어 있었다면 로그아웃 처리도 처리되어야 합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef unsigned long long ULL;
typedef unsigned int UI;
const int LM = (int) 5e6 + 5;
const int SIZE = 65537;
int N, regCnt, actCnt;
char id[15];
struct Node {
    ULL key;
    int active;
    Node* next;
    Node* alloc(ULL nk, Node *np) {
        key = nk, active = 0, next = np;
        return this;
    }
}buf[LM], htab[SIZE];
int bCnt;
ULL getKey(char *s) {
    ULL key = 0;
    for (int i = 0; s[i]; ++i) {
        key = key * 37 + s[i] - 47 - (s[i] > '9') * 39;
    }
    return key;
}
Node *probing(ULL key, int hidx) {
    Node *p = htab + hidx;
    for (; p->next; p = p->next) {
        if (p->next->key == key)
            return p;
    }
    return p;
}
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    int i, cmd, ret;
    for (i = 0; i < N; ++i) {
        scanf("%d %s", &cmd, id);
        ULL key = getKey(id);
        int hidx = key % SIZE;
        Node *p = probing(key, hidx);
        if (cmd == 1) {
            ret = !!p->next;
        }
        else if (cmd == 2) {
            ret = p->next && p->next->active;
        }
        else if (cmd == 3) {
            if (p->next)
                ret = regCnt;
            else {
                p->next = buf[bCnt++].alloc(key, NULL);
                ret = ++regCnt;
            }
        }
        else if (cmd == 4) {
            if (!p->next)
                ret = regCnt;
            else {
                if (p->next->active)
                    actCnt--;
                ret = --regCnt;
                p->next = p->next->next;
            }
        }
        else if (cmd == 5) {
            if (p->next && p->next->active == 0) {
                p->next->active = 1;
                actCnt++;
            }
            ret = actCnt;
        }
        else {
            if (p->next && p->next->active) {
                p->next->active = 0;
                actCnt--;
            }
            ret = actCnt;
        }
        printf("%d\n", ret);
    }
}

 

djb2 Version

#include <stdio.h>
 
typedef unsigned int UI;
const int LM = (int)5e5 + 5; // 50만
const int SIZE = 1 << 19; // 65537(2의 16승 + 1) -> prime
const int MOD = (SIZE - 1);
int N, regCnt, loginCnt;
 
int strcmp(const char* s, const char* t) {
    while (*s && *s == *t) ++s, ++t;
    return *s - *t;
}
 
struct Node {
    char key[13]; //id
    int act;
    Node* next;
    Node*alloc(Node* np) {
        act = 0;
        next = np;
        return this;
    }
    bool operator==(Node& r) {
        return strcmp(key, r.key) == 0;
    }
}buf[LM], hashTable[SIZE]; // hashTable[i][0]는 더미노드 역할
int bcnt;
 
UI djb2(char* s) {
    UI hash = 5381;
    for (; *s; ++s)
        hash = hash * 33 + *s;
    return hash & MOD;
}
 
Node* probing(int idx) {
    Node* p = hashTable + idx; // 더미 노드
    for (; p->next; p = p->next) {
        if (*(p->next) == buf[bcnt]) return p;
    }
    return NULL;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    int cmd;
    for (int i = 0; i < N; ++i) {
        scanf("%d %s", &cmd, buf[bcnt].key);
        int hIdx = djb2(buf[bcnt].key);
        Node *p = probing(hIdx);
        if (cmd == 1) {
            printf("%d\n", !!p);
        }
        else if (cmd == 2) {
            if (p) printf("%d\n", p->next->act);
            else puts("0");
        }
        else if (cmd == 3) {
            if (!p) {
                hashTable[hIdx].next = buf[bcnt++].alloc(hashTable[hIdx].next); //더미 노드기떄문에 이렇게
                regCnt++;
            }
            printf("%d\n", regCnt);
        }
        else if (cmd == 4) {
            if (p) {
                if (p->next->act) loginCnt--;
                regCnt--;
                p->next = p->next->next;
            }
            printf("%d\n", regCnt);
        }
        else if (cmd == 5) {
            if (p && p->next->act == 0) {
                p->next->act = 1;
                loginCnt++;
            }
            printf("%d\n", loginCnt);
        }
        else {
            if (p && p->next->act) {
                p->next->act = 0;
                loginCnt--;
            }
            printf("%d\n", loginCnt);
        }
    }
}