글 읽기 - 해쉬를 이용하고 싶은데요 질문좀 부탁드리겠습니다

kkw564 7년 전 0

이렇게 단일 해쉬로 짜버리면 시간초과가 나나요?

왜 시간초과가 나는지 잘 모르겠네요.

#include <iostream>
#include <algorithm>
#include <stack>

using namespace std;

typedef struct _student 
{
	int num;
	int order;

}Student;
int order = 1;


bool comp(Student const& a, Student const& b) {
	
	return a.order > b.order;
}

Student stu[4000000];

int main()
{
	int n, m;
	int val;
	stack<int> s;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> val;
		
		//cout << "hash :: " << val % 2000000 << endl;
		// 해쉬에 이미 값이 있다면
		if (stu[val % 2000000].num != 0)
		{
			if (stu[val % 2000000].num == val)
				stu[val % 2000000].order = order;
			
			// 해쉬 테이블의 빈자리를 찾을 때 까지 돌린다.
			else
			{
				for (int j = 0; ; j++)
				{
					if (stu[val % 2000000 + j].num == 0)
					{
						stu[val % 2000000 + j].num = val;
						stu[val % 2000000 + j].order = order;
					break;
					}
				}
			}
		}
		// 값이 없다면 바로 넣는다.
		else
		{
			stu[val % 2000000].num = val;
			stu[val % 2000000].order = order;
		}

		order++;
	}
	
	sort(stu, stu + 2000000, comp);

	for (int i = 0; stu[i].num != 0; i++)
	{
		s.push(stu[i].num);
	//	cout << "num :: " << stu[i].num << " order :: " << stu[i].order << endl;
	}

	for (int i = 0; i < n; i++)
	{
		cout << s.top() << endl;
		s.pop();
	}
}

exqt 7년 전 1

cin/cout 말고 scanf/printf 사용해보시겠어요?

입출력이 많이 느려보이네요

kkw564 7년 전 0

지금 해쉬를 2000000으로 기준잡은거에 대해서는 문제가 없나요?

50만개의 값만 받아들이면 되기에, 모두 같은수라 가정해도 최대 100만이라 생각하는데

해쉬에는 문제가 없나요?

exqt 7년 전 1

100 4

20000000
00000000
20000000
00000000
이면 00000000 이 2번 출력됩니다
이외에도 01234212도 1234212로 나오고 n이 m보다 더 큰경우 스택에 값이 없는데 뽑아서 런타임에러가 발생합니다
빈자리 찾아서 넣는게 문제인거 같은데 저는 방법이 잘 안보이네요..

rubi1541 7년 전 1

네 해쉬 크기 자체 에는 문제가 없다고 생각되네요
테스트 해보실려면은
입력 값들을 맥스로 설정해 놓으시고
rand를 활용하여 임의의 값들은 넣의신뒤
Time.h의 clock() 을 사용하여 시간을 재면서 해보세요
저도 이방법으로 느린 구간들은 찾아서 해결햇어요.

rubi1541 7년 전 1

max 값들로 넣고 테스트 해봤는데

sort(stu, stu + 2000000, comp); 까지는 약 0.2초 정도 걸리네요 뒷부분에서는 런타임 에러나구요

kkw564 7년 전 0

뒷부분이 왜 ㅇ런타임 에러가 잡히는지 잘 모르겠네요. 이유를 알면 해겷을하는데 이유를 모르니.. ㅠㅠ

kkw564 7년 전 0

진짜 도움이 급합니다..

런타임 에러의 원인을 못찾겠습니다..

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef struct _student
{
	int num;
	int order;

}Student;


bool comp(Student const& a, Student const& b) {

	return a.order > b.order;
}

Student stu[11000000];
int order = 1;

int main()
{
	int n, m, t = 0;
	int val;

	scanf("%d%d", &n, &m);

	for (int i = 0; i < m; i++)
	{
		scanf("%d", &val);

		//cout << "hash :: " << val % 2000000 << endl;
		// 해쉬에 이미 값이 있다면
		if (stu[val % 2000000].num != 0)
		{
			if (stu[val % 2000000].num == val)
				stu[val % 2000000].order = order;

			// 해쉬 테이블의 빈자리를 찾을 때 까지 돌린다.
			else
			{
				for (int j = 0; ; j++)
				{
					if (stu[val % 2000000 + j].num == 0)
					{
						stu[val % 2000000 + j].num = val;
						stu[val % 2000000 + j].order = order;
						break;
					}
				}
			}
		}
		// 값이 없다면 바로 넣는다.
		else
		{
			stu[val % 2000000].num = val;
			stu[val % 2000000].order = order;
		}

		order++;
	}

	sort(stu, stu + 10500000, comp);

	//printf("----------------\n");
	for (t = 0; stu[t].num != 0; t++) 
	{
	//	printf("%d :: %d\n", t, stu[t].num);
	}

	//printf("----------------\n");
	for (int i = 0; i < n ; i++)
	{
		printf("%08d\n", stu[t - 1].num);
		t--;
	}
}

game2k 7년 전 0

일단

10 8
20103324
20133221
20133221
20093778
20140101
01234567
20093778
20103325

이런 입력만 줘도 잘못 출력되네요

kkw564 7년 전 0

20103324
20133221
20140101
01234567
20093778
20103325

00000000

이렇게 출력해야 하나요? 아니면 00000000 이부분을 없애야하나요?

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef struct _student
{
	int num;
	int order;

}Student;


bool comp(Student const& a, Student const& b) {

	return a.order > b.order;
}

Student stu[11000000];
int order = 1;

int main()
{
	int n, m, t = 0;
	int val;

	scanf("%d%d", &n, &m);


	for (int i = 0; i < 11000000; i++)
	{
		stu[i].num = -1;
	}

	for (int i = 0; i < m; i++)
	{
		scanf("%d", &val);

		//cout << "hash :: " << val % 2000000 << endl;
		// 해쉬에 이미 값이 있다면
		if (stu[val % 2000000].num != -1)
		{
			if (stu[val % 2000000].num == val)
				stu[val % 2000000].order = order;

			// 해쉬 테이블의 빈자리를 찾을 때 까지 돌린다.
			else
			{
				for (int j = 0; ; j++)
				{
					// 찾는 도중 그 자리에 값이 같은 값이라면
					if (stu[val % 2000000 + j].num == val)
					{
						stu[val % 2000000 + j].order = order;
						break;
					}

					if (stu[val % 2000000 + j].num == -1)
					{
						stu[val % 2000000 + j].num = val;
						stu[val % 2000000 + j].order = order;
						break;
					}
				}
			}
		}
		// 값이 없다면 바로 넣는다.
		else
		{
			stu[val % 2000000].num = val;
			stu[val % 2000000].order = order;
		}

		order++;
	}

	sort(stu, stu + 10500000, comp);

	//	printf("----------------\n");
	for (t = 0; stu[t].num != -1; t++)
	{
		//			printf("%d :: %d\n", t, stu[t].num);
	}

	//printf("----------------\n");
	for (int i = 0; i < n; i++)
	{
		printf("%.8d\n", stu[t - 1].num);
		t--;
	}
}

kkw564 7년 전 1

이 코드를 쓰니 맞았다고 뜨네요

10 8
20103324
20133221
20133221
20093778
20140101
01234567
20093778
20103325

이 입력을

20103324
20133221
20140101
01234567
20093778
20103325
00000000
00000000
00000000
00000000

이렇게 출력하던걸

20103324
20133221
20140101
01234567
20093778
20103325

이렇게 나오게 했는데 맞았다 뜨네요

물론 안나오게 하는건맞는것같은데 저게 왜 런타임 에러를 유발하죠? 틀렸습니다면 이해하겠는데 저거때문에 런타임에러인가요?

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef struct _student
{
	int num;
	int order;

}Student;


bool comp(Student const& a, Student const& b) {

	return a.order > b.order;
}

Student stu[11000000];
int order = 1;
int cnt = 0;

int main()
{
	int n, m, t = 0;
	int val;

	scanf("%d%d", &n, &m);


	for (int i = 0; i < 11000000; i++)
	{
		stu[i].num = -1;
	}

	for (int i = 0; i < m; i++)
	{
		scanf("%d", &val);

		//cout << "hash :: " << val % 2000000 << endl;
		// 해쉬에 이미 값이 있다면
		if (stu[val % 2000000].num != -1)
		{
			if (stu[val % 2000000].num == val)
				stu[val % 2000000].order = order;

			// 해쉬 테이블의 빈자리를 찾을 때 까지 돌린다.
			else
			{
				for (int j = 0; ; j++)
				{
					// 찾는 도중 그 자리에 값이 같은 값이라면
					if (stu[val % 2000000 + j].num == val)
					{
						stu[val % 2000000 + j].order = order;
						break;
					}

					if (stu[val % 2000000 + j].num == -1)
					{
						stu[val % 2000000 + j].num = val;
						stu[val % 2000000 + j].order = order;
						break;
					}
				}
			}
		}
		// 값이 없다면 바로 넣는다.
		else
		{
			stu[val % 2000000].num = val;
			stu[val % 2000000].order = order;
		}

		order++;
	}

	sort(stu, stu + 10500000, comp);

	//	printf("----------------\n");
	for (t = 0; stu[t].num != -1; t++)
	{
		//			printf("%d :: %d\n", t, stu[t].num);
	}

	//printf("----------------\n");

	cnt = t;
	for (int i = 0; i < n && i < cnt; i++)
	{
		printf("%.8d\n", stu[t - 1].num);
		t--;

	}
}

ychooni 5년 전 1

런타임 이유가, s가 비어있는데, s.top() 이나, s.pop() 을 시도해서 그런거 같아요!!

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

문제

문제

출처

ICPC

해쉬를 이용하고 싶은데요 질문좀 부탁드리겠습니다

kkw564 7년 전 0

exqt 7년 전 1

kkw564 7년 전 0

exqt 7년 전 1

rubi1541 7년 전 1

rubi1541 7년 전 1

kkw564 7년 전 0

kkw564 7년 전 0

game2k 7년 전 0

kkw564 7년 전 0

kkw564 7년 전 1

ychooni 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말