[CodeForces] C. Registration system - 해시 테이블 구현

Problem - C - Codeforces

예제

4
abacaba
acaba
abacaba
acab

ans : 
OK
OK
abacaba1
OK
------------------------------------
6
first
first
second
second
third
third

ans : 
OK
first1
OK
second1
OK
third1

 

---

Codeforces Beta Round 4의 C번 문제이다. n개의 입력이 주어지는데, 처음 주어지는 문자열이면 OK를 출력하고 아니라면 그 문자열과 그 문자열이 입력된 횟수만큼 붙여서 출력하는 문제이다. 

 

문제의 특징은 탐색이 굉장히 빈번히 일어난다는 것이다. 그렇다고 완전 탐색으로 구현하기엔 최대 입력이 10^5이므로 무조건 시간 초과가 날 것이다. 이렇게 굉장히 많은 데이터에 대해 탐색이 빈번하게 일어난다면 해시테이블을 사용할 수 있다. 해시테이블을 구현하려면 먼저 충돌 회피 방안을 정하고, 그에 따라 테이블의 사이즈와 해시 함수를 정하면 된다. 물론 구현되어 있는 stl을 사용하는 게 가장 편하고 정확한 방법이지만 이번에는 직접 구현해 보았다.

 

해시함수는 문자열을 순회하면서 각 문자의 아스키코드에 소수를 곱해주고 다음 문자로 넘어가는 방식으로 정했다. 이런 식으로 소수를 곱해주는 방법이 간단히 생각할 수 있는 방법 중에 충돌이 일어날 확률을 가장 줄여주는 방법이다.

 

int hashing(string s)
{
    int key = 0;
    for (auto x : s)
    {
        key = (key * 31 + (int)x) % TABLE_SIZE;
    }
    return key % TABLE_SIZE;
}

다음으로 테이블 사이즈를 정해야 하는데, 나는 체이닝 기법으로 구현하려고 테이블 사이즈를 좀 크게 잡았다. 사실 체이닝 기법이면 최대 입력 크기로 잡아도 무관하지만 시간제한이 꽤 여유로워서 1000*400 크기의 테이블로 잡았다. 주의할 점은 각 문자열이 몇 번 들어왔는지 알아야 해서 table_cnt 이차원 배열을 따로 뒀다. 이 배열은 해시테이블과 똑같은 기능을 하지만 value로 문자열을 저장하는 게 아니라 해당 문자열이 들어온 횟수를 저장하였다.

 

나머지 구현은 크게 어려운 부분은 없었다.

/** 해시 Registration system **/
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int hashing(string s);
int find_table(string s, int key);
vector<vector<string>> table(1000, vector<string>(400));
vector<vector<int>> table_cnt(1000, vector<int>(400));
int length[1000] = {
    0,
}; // 각 테이블에 체이닝되어있는 원소 수를 나타낸다.
const int TABLE_SIZE = 1000;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        string s;
        cin >> s;

        int key = hashing(s);
        int cnt = find_table(s, key);

        // 이미 들어온 문자라면 출력
        if (cnt != -1)
        {
            cout << s << cnt << "\n";
        }
        else
        {
            // 들어온 적 없다면 OK출력 후 테이블 및 length 배열, table_cnt 갱신
            cout << "OK\n";
            table_cnt[key][length[key]] = 1;
            table[key][length[key]++] = s;
        }
    }
}

int hashing(string s)
{
    int key = 0;
    for (auto x : s)
    {
        key = (key * 31 + (int)x) % TABLE_SIZE;
    }
    return key % TABLE_SIZE;
}

int find_table(string s, int key)
{
    // table[key]에 s가 해당 s가 지금까지 출력된 횟수 리턴있으면  아니면 -1 리턴
    for (long i = 0; i < length[key]; i++)
        if (table[key][i] == s)
            return table_cnt[key][i]++;
    return -1;
}