글 읽기 - 왜 시간초과가 나는지 모르겠습니다.

werq20003 1년 전 1

분명 제대로 된 해시 알고리즘을 구현하여 썼다고 생각하는데 왜 시간초과가 나는걸까요?

어디에서 나는지 알려주시면 정말 감사하겠습니다.

#include <bits/stdc++.h>

#define MAX_TABLE 700001

using namespace std;

struct Node{

        string str;
        Node *next;

};

Node head[MAX_TABLE];
Node node[MAX_TABLE];
int node_cnt;
int result;

int hashing(string input){

        int div = 401;

        int i = 0;
        int len = input.length();

        while(i !=  len){
                div = ((div << 5) + (int)input[i]) % MAX_TABLE;
                i++;
        }

        return div % MAX_TABLE;

}

void insert_list(string input){

        int key = hashing(input);

        Node *temp = &head[key];
        Node *target = &node[node_cnt++];

        target->str = input;

        if(temp->next == 0){
                temp->next = target;
                result++;
        }
        else{
                while(temp->next != 0){
                        if(temp->next->str == input){
                                return;
                        }
                        temp = temp->next;
                }
                temp->next = target;
                result++;
        }

        return;

}

int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        string input;

        cin >> input;

        string temp;

        temp.clear();

        for(register int i = 0; i < input.length(); i++){
                for(register int j = i; j < input.length(); j++){
                        temp += input[j];
                        insert_list(temp);
                }
                temp.clear();
        }

        cout << result << '\n';

        return 0;

}

werq20003 1년 전 0

자문자답이네요

해싱할 때 문자열의 길이가 너무 길어서 연산할 때 시간이 오랜걸린 거였네요

vanava 1년 전 0

혹시 해싱 알고리즘을 어떻게 간략화 시키셨는지 알 수 있을까요 비슷한 문제를 겪고있는데 너무 마음이 힘드네요

부탁드립니다

werq20003 1년 전 1

19번째줄 key값을 생성할때 문자열의 길이만큼 다 더한뒤 key값을 구하고 있습니다.

그러면 현재 입력값이 1000길이의 문자열이 들어올 수가 있는데 이 길이가 너무 길어서 그걸 일일이 다 계산하고 key값을 구해서 시간초과가 떴습니다.

그래서 저는 26번째 while(i != len/4) 이런식으로 전체 길이가 아니라 4, 5 등으로 나누어서 연산하도록 만들었습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 시간초과가 나는지 모르겠습니다.

werq20003 1년 전 1

werq20003 1년 전 0

vanava 1년 전 0

werq20003 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말