[APA254] Assignment 03-Q1 solution

본 문제의 저작권은 한양대학교에 있습니다.

문제

The first row in the input file indicates the number of rows in data. The below input file contains 24 lines of (name and back number) of football players. For example, Christano Ronaldo have a back number 7 playing for Manchester United (ronaldo 7). Each row will be added to the hash table in order (1, 2, 3, 4 …) along with the unique back number. If there is a duplicate of player name, then print its adding order and back numbers, please refer the last three rows in output.

Input file

startlineup_menu.txt

24
lindelof 2
bailly 3
jones 4
macquire 5
varane 19
dalot 20
shaw 23
telles 27
pogba 6
mata 8
lngard 14
pereira 15
amad 16
pellistri 28
ronaldo 7
martial 9
rashford 10
greenwood 11
cavani 21
sancho 25
elanga 36
ronaldo 7
jones 4
pereira 15

Output

1 2
2 3
3 4
4 5
5 19
6 20
7 23
8 27
9 6
10 8
11 14
12 15
13 16
14 28
15 7
16 9
17 10
18 11
19 21
20 25
21 36
15 7
3 4
12 15

해설

이 문제는 해시테이블에 데이터를 저장하고 그 데이터가 저장된 위치를 출력하는 문제이다.

먼저 정의된 해시테이블을 보면서 데이터가 어떻게 저장되는지 확인해보자.

struct Hash {
    char str[23]; // 저장할 문자열 (최대 22자)
    int id, value; // 저장할 데이터 (아이디, 백넘버)
    Hash* next; // 다음 데이터를 저장할 공간
    Hash* alloc(char _str[], int _value, Hash* _next) { // 새로운 데이터를 저장하는 함수
        strcpy(str, _str); // 문자열 저장
        value = _value; // 백넘버 저장
        next = _next; // 다음 데이터 저장할 공간 저장
        id = ++strID; // 아이디 저장
        return this;
    }
}hbuf[200003], *htab[SIZE]; // 해시테이블, 해시테이블의 시작주소

구조체 Hash는 문자열과 백넘버, 다음 데이터를 저장할 공간을 가리키는 포인터를 가지고 있다. alloc()함수는 문자열, 백넘버, 다음 데이터를 가리키는 포인터를 저장하도록 하는 함수다. 이런 Hash가 200003개 있는 배열 hbuf[]가 실제 데이터들이 저장되는 공간이고, 포인터들의 배열 htab[SIZE]은 각 연결리스트의 시작주소를 담는다.

주어진 해시함수를 살펴보자.

unsigned long hash(char *str)
{
    int code = 0;
    for (int i = 0; str[i]; i++) {
        if (str[i] < 'a') str[i] += 32;
        code = (code * 27 + str[i] - 'a' + 1) & MASK;
    }
    return code;
}

이 함수는 문자열이 주어지면 각 문자에 대하여 다음 계산을 수행한다.

1. 문자가 대문자이면 소문자로 변환한다.
2. 해당 문자가 알파벳의 몇 번째 숫자인지 찾는다.
3. 기존 code에 27을 곱하고 해당 문자의 알파벳 순서를 더한다.
4. code의 값에 MASK를 &연산하여 계산 값을 반환한다. (주어진 코드의 MASK는 2진법으로 111111111111111111이므로 뒷 18자리만 취한다고 보면 되겠다.)

예를 들어 문자열 "cat"이 주어지면 아래와 같은 계산을 수행한다.

1. 'c'는 알파벳의 3번째 숫자이므로 code의 값은 $0 \times 27 + 3 = 3$이 된다.
2. 'a'는 알파벳의 1번째 숫자이므로 code의 값은 $3 \times 27 + 1 = 82$가 된다.
3. 't'는 알파벳의 20번째 숫자이므로 code의 값은 $82 \times 27 + 20 = 2234$가 된다.

이후 probing()함수를 통해 선언해둔 Hash hbuf[]에 문자열과 값을 저장한다. 주어진 probing()함수는 아래와 같이 작성되어 있다.

Hash* probing() {
    int hidx = hash(str);
    for (Hash* p = htab[hidx]; p; p = p->next) {
        if (!strcmp(str, p->str)) {
            if (value > p->value) p->value = value;
            return p;
        }
    }
    htab[hidx] = hbuf[hcnt++].alloc(str, value, htab[hidx]);
    return htab[hidx];
}

변수 hidx에 문자열을 해시함수를 적용하여 계산한 값을 저장하고, htab[hidx]에 해당 값이 없으면 htab[hidx]에 hbuf[hcnt++]를 저장한다. (hcnt는 현재 저장된 데이터의 개수) 만약 htab[hidx]에 해당 값이 있으면 새로운 값과 기존 값의 value를 비교하여 더 큰 값을 저장한다.

작성된 최종 main()함수는 다음과 같다. 파일에서 선수 데이터를 한 줄씩 읽어오면서 probing()함수를 통해 선수 데이터를 저장한다. 이후 저장된 데이터를 모두 출력한 뒤, 파일의 마지막 3줄을 읽어와 해당 데이터들이 어디에 저장되어있는지 정보를 출력한다.

int main() {
    // hide until deadline
    return 0;
}