[BOJ] 백준 7785 회사에 있는 사람

출처: https://www.acmicpc.net/problem/7785

 Input 

4

Baha enter

Askar enter

Baha leave

Artem enter

 

 Output 

Askar

Artem

▶ [해시] Hash란?

[해시] Hash란?

STL

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <functional>
using namespace std;
map<string, bool> member;
int main(){
    // freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int N; cin >> N;
    vector<string> vec;
    for (int i = 0; i < N; i++){
        string name, state;
        cin >> name >> state;
        // 이미 등록된 이름인 경우
        if (member.count(name)) {
            if (state == "enter")
                member[name] = true;
            else
                member[name] = false;
        }
        else {
            vec.push_back(name);
            member[name] = true;
        }
    }
    sort(vec.begin(), vec.end(), greater<string>());
    for (int i = 0; i < vec.size(); ++i) {
        if (member[vec[i]])
            cout << vec[i] << "\n";
    }
}

 

Hash 직접 구현

- 문자열 해시 이용(djb2 함수)

    : 회사원의 출/퇴근 상태 정보 저장

- 병합 정렬

    : 출근 중인 회사원을 역순으로 정렬

    : class의 연산자 중복 정의 이용 (bool operator <)

#include <stdio.h>
 
int strcmp(const char* s, const char* t) {
    while (*s && *s == *t) s++, t++;
    return *s - *t;
}
 
void strcpy(char* dest, const char* src) {
    while (*dest++ = *src++);
}
 
const int MAX_N = 1e6;
const int SIZE = 1 << 18;
const int STRLEM = 7;
int N, bcnt;
 
struct member {
    char name[STRLEM];
    bool operator <(const member& target) const {
        if (strcmp(name, target.name) > 0)
            return true;
        return false;
    }
} temp[MAX_N], arr[MAX_N];
 
 
void mergeSort(member* arr, int s, int e) {
    if (s >= e) return;
 
    // 1. divide
    int m = (s + e) / 2;
 
    // 2. conquer
    mergeSort(arr, s, m);
    mergeSort(arr, m + 1, e);
 
    // 3. merge
    int i = s, j = m + 1, k;
    for (k = s; k <= e; ++k) {
        if (i > m) temp[k] = arr[j++];
        else if (j > e) temp[k] = arr[i++];
        else if (arr[i] < arr[j]) temp[k] = arr[i++];
        else temp[k] = arr[j++];
    }
 
    // 4. copy
    for (i = s; i <= e; ++i) {
        arr[i] = temp[i];
    }
}
 
struct Node {
    char name[STRLEM];
    bool state;
    Node* next;
 
    Node* alloc(char name[], Node *np) {
        strcpy(this->name, name); 
        state = true; 
        next = np;
        return this;
    }
 
}buf[MAX_N], *htab[SIZE];
 
int djb2(char* s) {
    int hash = 5381;
    for (; *s; ++s)
        hash = hash * 33 + *s;
    return hash % SIZE;
}
 
Node* probing(int hidx, char name[]) {
    Node* p = htab[hidx];
    for (; p ; p = p->next) {
        if (strcmp(p->name, name) == 0) {
            return p;
        }
    }
    return NULL;
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    char name[STRLEM], state[STRLEM];
    
    for (int i = 0; i < N; ++i) {
        scanf("%s %s", name, state);
 
        int hidx = djb2(name);
        Node* p = probing(hidx, name);
        if (strcmp(state, "enter") == 0) {
            // 기존에 존재하는 회사원인 경우 (출근 상태로 변경)
            if (p) p->state = true;
            // 새롭게 등록되는 회사원인 경우 (Hash Table에 추가)
            else  htab[hidx] = buf[bcnt++].alloc(name, htab[hidx]);
        }
        else { // leave
            // 등록된 회사원인 경우, 퇴근 상태로 변경
            if(p) p->state = false;
        }
    }
 
    // 출근 상태인 회사원 정보 추출
    int total = 0;
    for (int i = 0; i < bcnt; i++) {
        if (buf[i].state) {
            strcpy(arr[total++].name, buf[i].name);
        }
    }
    
    // 역순 정렬
    mergeSort(arr, 0, total - 1);
 
    for (int i = 0; i < total; ++i) {
        printf("%s\n", arr[i].name);
    }
}