유년

유년

개발자

[SWEA] 9467. 문자열 암호화 (C++, 라이브러리 X)

B형 실전 문제

풀이

바꾸는 문자열이 3글자로 고정돼있으므로 Hash를 이용하면 1대1 매핑이 가능하다.

문자열의 크기 (50000), change 호출 횟수(50000) 을 고려하면 완전 탐색은 50000 * 50000 로 시간초과가 난다.

그래서 Hash Table을 Linked List 로 만들어 원하는 Hash에 바로 접근할 수 있도록 한다.

Worst Case

Hash Table을 이용해도 한번의 change 호출에 문자열 교체가 매우 많이 일어나는 경우에는 50000 * 50000 / 3 으로 시간초과가 날 수밖에 없다.

그러나 이러한 극단적인 Worst Case는 고려하지 않고, 입력이 랜덤으로 들어온다고 가정하여 푸는 것이 좋다고 한다.

실수

원래는 Single Linked List를 구현하였다.

구현 도중에 Double Linked List로 설계를 바꿨다. (삽입과 삭제가 빈번하게 일어나므로 Double을 사용하는게 좋다)

prev를 뒤늦게 추가하는 과정에서 실수가 있었다.

중간에 설계를 바꿀 경우 실수할 확률이 높으므로 처음부터 철처하게 설계하도록 하자.

코드 GitHub

#define MAXN 50005
#define HASH_SIZE (1<<15)

struct Node {
    int idx;
    Node* next;
    Node* prev;

    Node* Alloc(int _idx,Node* _prev, Node* _next) {
        idx = _idx;
        prev = _prev;
        next = _next;
        if(_next) _next->prev = this;
        if(_prev) _prev->next = this;

        return this;
    }
} nodes[MAXN];

char str[MAXN];
int N;
Node hashTable[HASH_SIZE];

int getHash(char *A) {
    int hash = *A++ - 'a';
    hash = (hash << 5) + *A++ - 'a';
    hash = (hash << 5) + *A - 'a';
    return hash;
}

int getNext(int hash, char *A) {
    hash &= (1 << 10) - 1;
    hash = (hash << 5) + *(A+3) - 'a';

    return hash;
}

int getPrev(int hash, char *A) {
    hash = hash >> 5;
    hash += (*A - 'a') << 10;

    return hash;
}

void mstrcpy(char *dst, char *src) {
    while(*src) *dst++ = *src++;
    *dst = 0;
    return;
}

void InputHash(Node* node, int hash) {
    Node* pivot = &hashTable[hash];
    while(pivot->next) {
        if(pivot->next->idx > node->idx) break;
        pivot = pivot->next;
    }
    node->next = pivot->next;
    pivot->next = node;
    node->prev = pivot;
    if(node->next) node->next->prev = node;

    return;
}

void init(int _N, char init_string[]) {
    N = _N;
    mstrcpy(str, init_string);
    for(int i = 0; i < HASH_SIZE; i++) hashTable[i].Alloc(-1, nullptr, nullptr);
    int hash = getHash(init_string + N - 3);
    hashTable[hash].next = nodes[N - 3].Alloc(N - 3, &hashTable[hash], hashTable[hash].next);
    for(int i = N - 4; i >= 0; i--) {
        hash = getPrev(hash, &init_string[i]);
        hashTable[hash].next = nodes[i].Alloc(i, &hashTable[hash], hashTable[hash].next);
    }

    return;
}

int change(char A[], char B[]) {

    int hashA = getHash(A);

    Node *pivot = hashTable[hashA].next;
    hashTable[hashA].next = nullptr;
    int prevIdx = -3;

    int cnt = 0;
    while(pivot) {
        pivot->prev = nullptr;
        if(prevIdx + 3 > pivot->idx) {
            Node* tmp = pivot->next;
            InputHash(pivot, hashA);
            pivot = tmp;
            continue;
        }
        cnt++;
        prevIdx = pivot->idx;
        str[pivot->idx] = B[0];
        str[pivot->idx+1] = B[1];
        str[pivot->idx+2] = B[2];
        Node* tmp = pivot->next;
        while(tmp && prevIdx + 3 > tmp->idx) {
            tmp = tmp->next;
        }
        int hash = -1;
        for(int i = pivot->idx - 2; i <= pivot->idx + 2; i++) {
            if(i < 0) continue;
            else if(i == N - 2) break;
            if(hash == -1) hash = getHash(str + i);
            else hash = getNext(hash, str + i - 1);

            if(nodes[i].prev) nodes[i].prev->next = nodes[i].next;
            if(nodes[i].next) nodes[i].next->prev = nodes[i].prev;
            Node* aa = &hashTable[33];

            InputHash(nodes + i, hash);
        }
        pivot = tmp;
    }

    return cnt;
}

void result(char ret[]) {
    mstrcpy(ret, str);
    return;
}

댓글남기기