글 읽기 - c++ 시간 줄이는 법

lshsys78 1년 전 0

cin cout 사용해서 출력해보았는데 900ms 넘는 시간이 나왔어요 ㅠㅠ

그래서 입출력 부분만 scanf printf 로 바꾸어보았는데 시간초과가 나더라구요..

어느 부분에서 시간이 오래걸렸을지 궁금해서 질문 드립니다 !

#include <iostream>
#include <string>
#include <map>
#pragma warning (disable:4996)
using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	map<int, int> mp;

	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int num; cin >> num;
		mp[num] = mp[num] + 1;
	}

	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		int num; cin >> num;
		cout << ("%d", mp[num]) << " ";
	}
}

/////////////////////////////////////////


// 아래 코드는 scanf, printf 로 바꾸어서 제출 했지만 시간 초과가 뜬 코드
#include <iostream>
#include <string>
#include <map>
#pragma warning (disable:4996)
using namespace std;

int main() {
	map<int, int> mp;

	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int num; scanf("%d", &num);
		mp[num] = mp[num] + 1;
	}

	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		int num; scanf("%d", &num);
		printf("%d ", mp[num]);
	}
}

zenith82114 1년 전 1

cin도 scanf로 바꿔주셔야 합니다.

cin-cout이랑 scanf-printf 섞어쓰면 더 느려지거나 틀릴 수도 있어요.

djm03178 1년 전 1

map이 그만큼 무거운 자료구조입니다. 균형 이진 트리라는 것이 그렇게 가볍지 않습니다.

조금 개선할 수 있는 부분이라면 mp[num] = mp[num] + 1로 쓰는 것보다는 ++mp[num]으로 하는 것이 빠릅니다. 전자는 mp[num]을 두 번 호출하고 그 때마다 트리 내에서 O(logN) 시간의 탐색이 발생하는데, 후자는 이 횟수를 하나로 줄일 수 있습니다.

djm03178 1년 전 2

그리고 cout을 쓰는데 %d를 쓴 건 무의미한 문장입니다. ("%d", mp[num])이라는 식 자체가 콤마 연산자의 동작 원리에 따라 좌항이 아무 역할도 하지 않고 그대로 버려지고 mp[num]만 값으로 취했기 떄문에 동작이 되었을 뿐입니다. 그냥 cout << mp[num] << " ";이면 충분합니다.

lshsys78 1년 전 0

감사합니다 !! ㅠㅠ

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

문제

문제

출처

ICPC

c++ 시간 줄이는 법

lshsys78 1년 전 0

zenith82114 1년 전 1

djm03178 1년 전 1

djm03178 1년 전 2

lshsys78 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말