unordered_map을 이용한 노드 개수 최적화

알고리즘 문제를 풀다가 이런 문제를 발견했다. 

 

다익스트라 문제인데 노드는 50개 뿐이지만 노드의 번호 범위가 무려 1~10억이었다.

다익스트라는 dp기반이기 때문에 dp[노드의개수]로 맞춰놓는 것이 일반적이다. 그런데 dp[10억]은 엄청난 메모리 낭비를 초래한다.

 

그래서 사용할 수 있는 방법이 바로 unordered_map을 이용한 노드 개수 최적화이다.

 

unordered_map는 자동으로 키값으로 정렬하는 맵과 달리 정렬하지 않는 해싱기법이다.

 

unordered_map<int, int> nodes;

int get_idx(int v) {
	return nodes[v];
}

 

먼저 맵을 선언해두고 인덱스를 겟할 수 있는 함수를 만들어준다.

 

for (int i = 0; i < N; i++) {
		if (nodes.count(원래노드[i]) == 0) nodes[원래노드[i]] = (int)nodes.size();
	}

 

그리고 문제 입력에 따라 먼저 노드값을 갱신해둔다. 이게 무슨 말이냐면, 해쉬맵은 해쉬충돌이 발생할 수 있어서 같은 키값에 두가지 값이 들어올 수 있다. 

 

예를들어 만약 5억이 들어왔다면 5억을 그대로 쓰는 것이 아니라 해쉬맵을 통해 0번으로 바꾸어버리는 것이다. 

 

 

이후에는 get_idx 함수로 바뀐 인덱스를 가지고 연산을 진행하면 된다.

동적할당보다 훨씬 메모리도 적게 사용할수 있고 unordered_map의 접근 시간은 O(1)이기 때문에 시간상에서도 많은 이득을 줄.. 수있나? 이거 써서 시간초과인 경우도 본 것 같은데..