글 읽기 - 시간 초과가 나오는데 어떻게 하면 줄일 수 있을까요

moda71929 1년 전 0

예제를 넣어봐도 답은 맞췄는데 정작 제출하면 시간 초과가 나네요;

vector에 이름을 넣고 map으로 그 이름이 몇 번 입력되었는지 카운트 해줬습니다.

그 후 입력이 종료되면 vector를 정렬하고 반복문으로 출력하도록 했는데, 아마 제 생각에는 30번째 줄의 find()때문에 시간 초과가 나는 것 같습니다.

혹시 find()대신 더 좋은 방법이 있을까요..?

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

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

	vector<string> name;
	map<string, double> count;

	int sum = 0;

	while (1) {
		string str;
		getline(cin, str);

		if (str == "") break;

		else {
			count[str] += 1;

			sum++;

			//같은 문자열이 벡터에 없을 때만 추가
			if (find(name.begin(), name.end(), str) == name.end()) name.push_back(str);
		}
		
	}

	//문자열을 사전순으로 정렬
	sort(name.begin(), name.end());

	//소수점 출력 범위 지정
	cout << fixed;
	cout.precision(4);

	for (auto x : name) {
		cout << x << " " << (count[x] / sum) * 100 << endl;
	}
}

moda71929 1년 전 0

30번째 줄을 find()가 아닌 map의 값으로 검사하도록 바꿔보니 성공했습니다.

제가 바보였네요ㅎ

아 그리고 double형을 1과 비교할려고 하니까 1 = 1.000000이 정확이 비교되는지 잘 몰라서 혹시 몰라 부등호를 사용했는데, 그냥 == 으로 비교해도 괜찮았던 걸까요?

if (count[str] <= 1) name.push_back(str);

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

문제

문제

출처

ICPC

시간 초과가 나오는데 어떻게 하면 줄일 수 있을까요

moda71929 1년 전 0

moda71929 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말