글 읽기 - unordered_map 사용 관련 도저히 이해가 안되어 질문 올립니다.

supergrammer 4년 전 0

주어진 문제에서 unordered_map을 이용해 답을 도출하고자 했습니다.

key 값이 a + b에 해당하는 해시 테이블 value 값을 1씩 증가시키고,
c, d 또한 똑같이 했습니다.

입력이 4천개인 직접 만들어 실험해 본 결과,

input, vector 삽입인 ipt() 함수에서 4ms,

a + b, c + d 값을 unorderd_map에 저장하는 mrg() 함수에서 89,000ms,

값을 도출하는 arrs() 에서 1ms (해시 테이블에 값이 몇 개 없어서 적게 나왔지만, O(n^2)을 넘지 않습니다.

가 나왔습니다.

문제는 mrg 함수에서 맵의 삽입에 O(n * n)이 나와야 하는데,

16,000,000을 두번 삽입하는 과정에서도 많이 쳐줘야 1초를 넘지 않습니다...

이유를 알고 싶습니다.

사용된 테스트케이스는

4000
-1 -1 1 1
...

입니다.

#include <iostream>
#include <vector>
#include <unordered_map>
#define F(x, y, z) for(int x=y;x<z;x++)
#define ll long long
using namespace std;

int N, in[4];
vector<int> V[4];
unordered_map<int, int> Mab, Mcd;

void ipt() {
	cin.sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	F(i, 0, N)F(j, 0, 4) {
		cin >> in[j];
		V[j].push_back(in[j]);
	}
}

void mrg() {
	F(i, 0, N)F(j, 0, N) {
		int ab = V[0][i] + V[1][j],
			cd = V[2][i] + V[3][j];
		Mab[ab]++; Mcd[cd]++;
	}
}

ll arrs() {
	ll sum = 0;
	for (auto a : Mab)
		if (Mcd.find(-a.first) != Mcd.end())
			sum += (ll)a.second * (ll)Mcd[-a.first];
	return sum;
}

int main() {
	ipt();
	mrg();
	cout << arrs();
}

djm03178 4년 전 1

질문을 잘 이해 못하겠는데, 제가 이해한 게 맞나요?

질문자님은 1600만씩 두 번을 넣더라도 1초를 넘어야 하지 않아야 한다고 생각하는데, 왜 89초나 걸렸는지 궁금하시다는 건가요?

supergrammer 4년 전 0

네 맞습니다...

심지어 같이 푼 사람은 합의 값을 양 벡터에 넣어 sort 과정까지 거친 후에 탐색을 전부 해도 전체 1,000ms를 조금 넘는 결과가 나왔네요...

djm03178 4년 전 0

일단 제 생각엔 빌드 설정을 debug 모드로 하신 게 아닐까 싶습니다. Release로 해보세요.

그리고 unordered_map은 평균이 O(1)이라는 것일 뿐 실제로는 해시 충돌의 횟수나 해시 resize의 횟수에 따라 성능 차이가 크게 날 수 있는 꽤 느린 자료구조입니다.

supergrammer 4년 전 0

다른 자료구조 이용해 풀어 보겠습니다...

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

문제

문제

출처

ICPC

unordered_map 사용 관련 도저히 이해가 안되어 질문 올립니다.

supergrammer 4년 전 0

djm03178 4년 전 1

supergrammer 4년 전 0

djm03178 4년 전 0

supergrammer 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말