C++ Map의 전역변수 설정여부에 따른 시간 변화 kwonmha NERD2 문제를 풀다가 코드를 책에 나온 것과 거의 동일하게 했는데 시간 초과가 나더라고요. 차이점이 있다면 책에는 map< int, int > coord를 전역변수로 설정했었고, 저는 메인 함수 안에다 선언하고 함수를 호출할 때마다 인자로 넘겨줬습니다. 그래서 책에 나온 방식대로 하니 되더라고요. 왜 이렇게 차이가 나는 건가요? map< int, int > coord를 인자로 넘겨주는게 시간이 그렇게 오래 걸리나요? 코드는 아래와 같습니다. #include <cstdio> #include <map> #pragma warning(disable:4996) using namespace std; bool IsDominated(map<int, int> coords, int a, int b){ map<int, int>::iterator cit = coords.upper_bound(a); if (cit == coords.end()) return false; return b < cit->second; } void RemoveDominated(map<int, int> &coords, int a, int b){ map<int, int>::iterator cit = coords.lower_bound(a); if (cit == coords.begin()) return; cit--; while (true){ if (cit->second > b) break; if (cit == coords.begin()){ coords.erase(cit); break; } else{ map<int, int>::iterator cit2 = cit; cit2--; coords.erase(cit); cit = cit2; } } return; } int CountPpl(map<int, int> &coords, int a, int b){ // 지배당하면 필요없다 if (!IsDominated(coords, a, b)){ // 지배하는 것들 지우기 RemoveDominated(coords, a, b); //coords.insert(coords.end(), make_pair(a, b)); coords[a] = b; } return coords.size(); } int main(void){ //freopen("input.txt", "r", stdin); int tc, ppl; map<int, int> coords; scanf("%d", &tc); for (int i = 0; i < tc; i++){ scanf("%d", &ppl); int a, b, count = 0; coords.clear(); for (int j = 0; j < ppl; j++){ scanf("%d %d", &a, &b); if (j == 0){ coords[a] = b; count += 1; continue; } count += CountPpl(coords, a, b); } printf("%d\n", count); } return 0; } 8년 전
4개의 댓글이 있습니다. VOCList IsDominated의 coords도 &로 받아보시져 8년 전 link kwonmha 오 그렇게 하니까 빠르게 풀리네요. 감사합니다. IsDominated에선 coords를 변경시킬 일이 없어서 쓰지 않았는데... 시간이 걸리는 원인은 IsDominated가 호출될 때 coords를 복사해서 그런 건가요? 8년 전 link wookayin 네 map<int, int> coords 이렇게 파라메터를 선언하시면, map 객체가 복사되어서 느립니다. 변경시킬 일이 없다면 const map<int, int> &coords 이렇게 const로 선언하면 좋습니다. 8년 전 link kwonmha 네 답변 감사합니다! 8년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
kwonmha
NERD2
문제를 풀다가 코드를 책에 나온 것과 거의 동일하게 했는데
시간 초과가 나더라고요.
차이점이 있다면 책에는 map< int, int > coord를 전역변수로 설정했었고, 저는 메인 함수 안에다 선언하고 함수를 호출할 때마다 인자로 넘겨줬습니다.
그래서 책에 나온 방식대로 하니 되더라고요.
왜 이렇게 차이가 나는 건가요?
map< int, int > coord를 인자로 넘겨주는게 시간이 그렇게 오래 걸리나요?
코드는 아래와 같습니다.
8년 전