글 읽기 - c++ / 시간을 줄일 수 있는 방법이 있을까요??

pppp1923 4년 전 0

현재 실행시간이 300ms인데 120대로 줄이려면 어떻게 해야할까요 ㅠㅠ

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

map<string, string> parent;
map<string, int> r;
map<string, int> cnt;

string Find(string s) {
	if (s == parent[s]) {
		return s;
	}
	else {
		return parent[s] = Find(parent[s]);
	}
}

void Union(string x, string y) {
	if (x == y) return;
	if (r[x] < r[y]) swap(r[x], r[y]); //always rank[x] >= rank[y]
	parent[y] = x;
	cnt[x] += cnt[y];
	if (r[x] == r[y]) r[x] = r[y] + 1;
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int test; cin >> test;
	while (test--) {
		int f; cin >> f;
		parent.clear(); r.clear(); cnt.clear();
		for (int i = 0; i < f; i++) {
			string user1, user2;
			cin >> user1 >> user2;
			if (parent[user1] == "") { //initialize
				r[user1] = 0;
				cnt[user1] = 1;
				parent[user1] = user1;
			}
			if (parent[user2] == "") { //initialize
				r[user2] = 0;
				cnt[user2] = 1;
				parent[user2] = user2;
			}
			user1 = Find(user1);
			user2 = Find(user2);
			Union(user1, user2);
			cout << cnt[user1] << "\n";
		}
	}
	return 0;
}

sait2000 4년 전 1

어디서 들은 바에 의하면 22번 줄같은 size 최적화가 시간복잡도를 줄이긴 하는데 실제로 문제에서 나오는 사이즈에서는 그닥 도움이 안 된다고 하는 말을 들은 적이 있는데 22번 줄을 주석처리하고 내보시죠

sait2000 4년 전 1

근데 그것보다는 key를 string을 그대로 사용해서 그런 것 같기도 하네요. map을 사용해서 문자열을 정수로 바꾸고 union find에 배열을 쓰면 빨라질 거 같아요

ckdgus2482 4년 전 2

윗분 말씀대로 정수로 바꾸는게 가장 좋고, string으로 하더라도 const string& 타입으로 바꾸세요

string을 매번 값 복사하고 있으니 복사 오버헤드 상당합니다

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

문제

문제

출처

ICPC

c++ / 시간을 줄일 수 있는 방법이 있을까요??

pppp1923 4년 전 0

sait2000 4년 전 1

sait2000 4년 전 1

ckdgus2482 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말