my devloping history.

5 분 소요

#include

#include “memory.h”

#define MAX_N 10000

typedef struct buff{

char data[10];

int size;

}buff;

buff p[MAX_N] = { 0, };

buff p_t[MAX_N] = { 0, };

//char p[MAX_N][10] = { 0, };

//char p_t[MAX_N][10] = { 0, };

unsigned long long hash[10][MAX_N] = { 0, };  // hash[n][0] is count.

unsigned long long mpow[10] = { 0, };

void merge_sort(int l, int r)

{

if (r - l < 1)

return;

int mid;

mid = (r + l) / 2;

merge_sort(l, mid);

merge_sort(mid + 1, r);

int idx, ll, lr;

idx = ll = l;

lr = mid + 1;

for (int i = l; i <= r; i++)

{

memcpy(p_t[i].data, p[i].data, sizeof(p[i].data));

p_t[i].size = p[i].size;

}

while (ll <= mid && lr <= r)

{

if (p_t[ll].size <= p_t[lr].size)

{

memcpy(p[idx].data, p_t[ll].data, sizeof(p_t[ll].data));

p[idx++].size = p_t[ll++].size;

}

else

{

memcpy(p[idx].data, p_t[lr].data, sizeof(p_t[lr].data));

p[idx++].size = p_t[lr++].size;

}

}

while (ll <= mid)

{

memcpy(p[idx].data, p_t[ll].data, sizeof(p_t[ll].data));

p[idx++].size = p_t[ll++].size;

}

while (lr <= r)

{

memcpy(p[idx].data, p_t[lr].data, sizeof(p_t[lr].data));

p[idx++].size = p_t[lr++].size;

}

}

//length check

#if 0

int a = 12345;

int size = 0;

for (int i = 0; i < 10; i++)

{

size++;

a = a / 10;

if (a == 0) break;

}

#endif

int my_size_check(char * value)

{

int size = 0;

for (int i = 0; i < 10; i++)

{

if (value[i] != ‘\0’)

size++;

else

break;

}

return size;

}

//calc hash table

unsigned long long my_pow(int x, int y)

{

unsigned long long result = 1;

for (int i = 0; i < y; i++)

{

result = result * x;

}

return result;

}

//1 * 275 + 2 * 275 * 275 + 3 * 275 * 275*275 + 4*275*275*275*275

//for test

#if 0

int a = 12345;

int b = 0;

for (int i = 4; i >= 0; i–)

{

b = a / my_pow(10, i);

a = a % my_pow(10, i);

}

#endif

#define HASH_DATA 257

unsigned long long current_hash[10] = { 0, };

void my_hash(char * x, int size)

{

unsigned long long hash_result = 0;

memset(current_hash, 0, sizeof(current_hash));

for (int i = 0; i < size; i++)

{

//hash_result = hash_result + (x[i]-‘0’) * my_pow(HASH_DATA, count++);

if (i == 0)

current_hash[i] = (x[i] - ‘0’) * mpow[i];

else

current_hash[i] = current_hash[i-1] + (x[i] - ‘0’) * mpow[i];

}

return;

}

int main(void)

{

int test_case = 0;

scanf(“%d”, &test_case);

for (int x = 0; x < 10; x++)

mpow[x] = my_pow(HASH_DATA, x);

for (int t = 0; t < test_case; t++)

{

int n = 0;

int size_pi = 0;

unsigned long long c_hash = 0;

int status = 0;

scanf(“%d”, &n);   // max 10000

memset(p, 0, sizeof(p));

memset(p_t, 0, sizeof(p_t));

memset(hash, 0, sizeof(hash));

for (int nn = 0; nn < n; nn++)

{

scanf(“%s”, &p[nn].data);

p[nn].size = my_size_check(p[nn].data);

}

//merge sort for lenght

merge_sort(0, n-1);

// length 별로 해시 저장?

for (int i = 0; i < n; i++)

{

//1st. check size

size_pi = p[i].size;

//2nd. hash table size 작은것 부터 비교.

// 동일하게 시작부터 연속된 번호가 있는지 확인한다.

my_hash(p[i].data, p[i].size);

for (int k = 0; k < 10; k++)

{

if (hash[k][0] != 0)

{

//c_hash = my_hash(p[i].data, k + 1, size_pi);

for (int kk = 1; kk <= hash[k][0]; kk++)

{

if (current_hash[k] == hash[k][kk])

{

status = 1;

goto END;

}

}

}

}

//3rd. size 끝날때에 hash table save.

//c_hash = my_hash(p[i].data, size_pi);

hash[size_pi - 1][0] = hash[size_pi - 1][0]++;

hash[size_pi - 1][hash[size_pi - 1][0]] = current_hash[size_pi-1];

//long long hash[10][MAX_N+4] = { 0, };  // hash[n][0] is count.

}

END:

if (status == 0)

printf(“YES\n”);

else

printf(“NO\n”);

}

return 0;

}

==>  수정

#include

#include “memory.h”

#define MAX_N 10000

typedef struct buff{

char data[10];

int size;

}buff;

buff p[MAX_N] = { 0, };

buff p_t[MAX_N] = { 0, };

//char p[MAX_N][10] = { 0, };

//char p_t[MAX_N][10] = { 0, };

unsigned long long hash[MAX_N][10] = { 0, };

//unsigned long long hash[10][MAX_N] = { 0, };  // hash[n][0] is count.

unsigned long long mpow[10] = { 0, };

void merge_sort(int l, int r)

{

if (r - l < 1)

return;

int mid;

mid = (r + l) / 2;

merge_sort(l, mid);

merge_sort(mid + 1, r);

int idx, ll, lr;

idx = ll = l;

lr = mid + 1;

for (int i = l; i <= r; i++)

{

memcpy(p_t[i].data, p[i].data, sizeof(p[i].data));

p_t[i].size = p[i].size;

}

while (ll <= mid && lr <= r)

{

if (p_t[ll].size <= p_t[lr].size)

{

memcpy(p[idx].data, p_t[ll].data, sizeof(p_t[ll].data));

p[idx++].size = p_t[ll++].size;

}

else

{

memcpy(p[idx].data, p_t[lr].data, sizeof(p_t[lr].data));

p[idx++].size = p_t[lr++].size;

}

}

while (ll <= mid)

{

memcpy(p[idx].data, p_t[ll].data, sizeof(p_t[ll].data));

p[idx++].size = p_t[ll++].size;

}

while (lr <= r)

{

memcpy(p[idx].data, p_t[lr].data, sizeof(p_t[lr].data));

p[idx++].size = p_t[lr++].size;

}

}

//length check

#if 0

int a = 12345;

int size = 0;

for (int i = 0; i < 10; i++)

{

size++;

a = a / 10;

if (a == 0) break;

}

#endif

int my_size_check(char * value)

{

int size = 0;

for (int i = 0; i < 10; i++)

{

if (value[i] != ‘\0’)

size++;

else

break;

}

return size;

}

//calc hash table

unsigned long long my_pow(int x, int y)

{

unsigned long long result = 1;

for (int i = 0; i < y; i++)

{

result = result * x;

}

return result;

}

//1 * 275 + 2 * 275 * 275 + 3 * 275 * 275*275 + 4*275*275*275*275

//for test

#if 0

int a = 12345;

int b = 0;

for (int i = 4; i >= 0; i–)

{

b = a / my_pow(10, i);

a = a % my_pow(10, i);

}

#endif

#define HASH_DATA 257

//unsigned long long current_hash[10] = { 0, };

void my_hash(char * x, int size, unsigned long long *hash)

{

//unsigned long long hash_result = 0;

//memset(current_hash, 0, sizeof(current_hash));

for (int i = 0; i < size; i++)

{

//hash_result = hash_result + (x[i]-‘0’) * my_pow(HASH_DATA, count++);

if (i == 0)

hash[i] = (x[i] - ‘0’) * mpow[i];

else

hash[i] = hash[i-1] + (x[i] - ‘0’) * mpow[i];

}

return;

}

int main(void)

{

int test_case = 0;

scanf(“%d”, &test_case);

for (int x = 0; x < 10; x++)

mpow[x] = my_pow(HASH_DATA, x);

for (int t = 0; t < test_case; t++)

{

int n = 0;

int size_pi = 0;

unsigned long long c_hash = 0;

int status = 0;

scanf(“%d”, &n);   // max 10000

memset(p, 0, sizeof(p));

memset(p_t, 0, sizeof(p_t));

memset(hash, 0, sizeof(hash));

for (int nn = 0; nn < n; nn++)

{

scanf(“%s”, &p[nn].data);

p[nn].size = my_size_check(p[nn].data);

}

//merge sort for lenght

merge_sort(0, n-1);

for (int i = 0; i < n; i++)

{

//1st. check size

size_pi = p[i].size;

//hash 값 저장.

my_hash(p[i].data, p[i].size, hash[i]);

}

// 짧은것부터 긴것들 조사..  (조사하려는 번호의 길이만 검색하면됨)

for (int i = 0; i < n; i++)

{

size_pi = p[i].size;

for (int j = i+1; j < n; j++)

{

if (hash[i][size_pi - 1] == hash[j][size_pi - 1])

{

status = 1;

goto END;

}

}

}

END:

if (status == 0)

printf(“YES\n”);

else

printf(“NO\n”);

}

return 0;

}

\

참고

1 분 소요

뇌피셜 속초 맛집과 갈 만한곳

최대 1 분 소요

송도 횟집 속초 앞바다에서 나는 가자미를 그날 그날 받아서 세꼬시 물회로 팝니다. 테카해서 드시면 미역국이랑 밥, 초장도 같이 제공해서 집에 가져와서 주로 먹습니다. ^^; 앞에 도로가 좁긴한데 차로 앞까지 올수 있으니 참고 하세요. 송도 횟집.