글 읽기 - c++ 입문자입니다

DryType 6년 전 0

map과 vector를 처음 써보는데 이렇게 쓰는게 맞나요?

자꾸 시간초과가 뜨네요 ㅠㅠ

어디부분이 시간이 많이 차지하는지 모르겠네요.

코드는 아래와 같습니다.

고수님들의 조언 부탁드리겠습니다.

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

int main()
{
	freopen("input.txt", "r", stdin);
	setbuf(stdout, NULL);
	int n, k;
	scanf("%d%d", &n, &k);

	map<string, int> m;
	vector<pair<int, string>> snum;

	for (int i = 0; i < k; i++)
	{
		string str = "";
		cin >> str;

		m[str] = i;
		//auto ret = m.insert(pair<string, int>(str, i));
		//if (!ret.second) m[str] = i;
	}

	for (auto ref = m.begin(); ref != m.end(); ref++)
	{
		snum.push_back(pair<int, string>(ref->second, ref->first));
	}
	sort(snum.begin(), snum.end());

	n = snum.size() < n ? snum.size() : n;
	for (int i = 0; i < n; i++)
	{
		cout << snum[i].second << endl;
	}
	return 0;
}

bupjae 6년 전 1

map과 vector 사용법은 잘못되지는 않았습니다만...

작성하신 프로그램의 시간복잡도는 O(n log n)입니다.

하지만 이 문제를 시간초과 없이 풀기 위해서는 O(n) 알고리즘이 필요합니다.

jjwdi0 6년 전 1

우선 std::map은 삽입, 삭제가 O(log n)에 이루어지기는 하나 매우 느리게 작동하고요.

위 코드에서는 특히 string형을 key로 사용해서 더 오래 걸리는 것 같습니다.

저는 입력값이 8자리 정수임을 착안해서 key를 int형으로 선언했습니다. 그러면 O(n log n)으로도 통과하실 수 있을 겁니다.

h0ngjun7 6년 전 2

bupjae님이 말씀하신 O(n) 알고리즘이 무엇인지는 잘 모르겠네요.

O(n log n)으로도 충분히 해결 가능합니다.

jjwdi0님이 말씀하신 것도 하나의 요인은 될 수 있지만, 본 프로그램에서 가장 주된 요인은 cin과 cout의 느린 수행 속도 때문입니다.

아래 코드는 300ms로 맞는 코드입니다.

ios::sync_with_stdio를 쓰시면 cin의 속도가 향상되며, cout << ~~~ << endl 보다는 puts( ~~~ )를 하시는 게 훨씬 빠릅니다.

기본적으로 C++ 입출력보다 C의 입출력이 빠르다는 점 참고하시면 되겠습니다.

그럼 string type의 데이터는 어떻게 입력받나 궁금하실 수 있는데,

저는 char buffer[100]={0,} 이런식으로 배열을 잡아 둔 후에, scanf("%s",buffer)를 한 후

string s = "";

for (int i = 0; buffer[i]; i++) s+= buffer[i];

이런 식으로 buffer에 있는 내용을 s에 옮깁니다.

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

int main()
{
	ios::sync_with_stdio(false);
	int n, k;
	cin >> n >> k;

	map<string, int> m;
	vector<pair<int, string>> snum;

	for (int i = 0; i < k; i++)
	{
		string str = "";
		cin >> str;

		m[str] = i;
		//auto ret = m.insert(pair<string, int>(str, i));
		//if (!ret.second) m[str] = i;
	}

	for (auto ref = m.begin(); ref != m.end(); ref++)
	{
		snum.push_back(pair<int, string>(ref->second, ref->first));
	}
	sort(snum.begin(), snum.end());

	n = snum.size() < n ? snum.size() : n;
	for (int i = 0; i < n; i++)
	{
        puts(snum[i].second.c_str());
	}
	return 0;
}

DryType 6년 전 0

댓글 달아주신분들 너무 감사합니다!

출력만 바꿨을 뿐인데 해결됐습니다.

앞으로 cin cout은 잘 안써야겠어요.

O(n)알고리즘 궁금합니다 ㅠㅠ map을 안써야 되는거죠?

bupjae 6년 전 0

map은 삽입/삭제 연산이 O(log n) 인데 비해, unordered_map 는 삽입/삭제 연산이 O(1) 입니다.

다만, unordered_map 은 iteration 순서가 정의되어 있지 않으므로 이를 보조하기 위해 list 또는 vector가 필요합니다.

unordered_map 과 (list 또는 vector) 를 조합하면 O(n) 으로 작성이 가능합니다.

DryType 6년 전 0

감사합니다 꼭 공부해보겠습니다

일단은 이렇게 풀었습니다. 200ms가 나오네요

#include <stdio.h>
#include <vector>
#include <unordered_map>
using namespace std;

int main()
{
	int n, k;
	int cnt = 0;
	scanf("%d%d", &n, &k);
	unordered_map<int, int>m2;
	vector<pair<int, int>> snum;

	for (int i = 0; i < k; i++)
	{
		int num;
		scanf("%d", &num);

		auto ret = m2.insert(pair<int, int>(num, i));
		snum.push_back(pair<int, bool>(num, true));
		if (!ret.second)
		{
			snum[m2.find(num)->second].second = false;
			m2[num] = i;
		}
	}

	for (int i = 0; i < k; i++)
	{
		if (snum[i].second)
		{
			printf("%.8d\n", snum[i].first);
			cnt++;
		}
		if (cnt == n) break;

	}
	return 0;
}

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

문제

문제

출처

ICPC

c++ 입문자입니다

DryType 6년 전 0

bupjae 6년 전 1

jjwdi0 6년 전 1

h0ngjun7 6년 전 2

DryType 6년 전 0

bupjae 6년 전 0

DryType 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말