글 읽기 - 시간 초과를 어떻게 해야 하나요?

bangbadak 4년 전 0

다시 짜서 만들어봤는데 이번엔 시간초과가 뜨네요.

어떻게 해야 시간을 줄일 수 있을까요?

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool sort1(string A, string B)
{
	auto a_it = A.begin(), b_it = B.begin();
	int i, c = 0, t = A.length() < B.length() ? A.length() : B.length();
	for (i = 0; i < t; i++, a_it++, b_it++)
		if (*a_it != *b_it)
			return *a_it < *b_it;
	return A.length() < B.length();
}
bool compare(string A, string B)
{
	auto a_it = A.begin(), b_it = B.begin();
	int i, c = 0, t = A.length() < B.length() ? A.length() : B.length();
	for (i = 0; i < t; i++, a_it++, b_it++)
	{
		if (*a_it < *b_it)
			return 1;
		else if(*a_it > *b_it)
			return 0;
	}
	return A.length() < B.length();
}
int main(void)
{
	int a, b, i, size = 0;
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> a >> b;
	vector<string> n(a), m(b), ans;
	//입력
	for (auto it = n.begin(); it != n.end(); it++)
		cin >> *it;
	for (auto it = m.begin(); it != m.end(); it++)
		cin >> *it;
	sort(n.begin(), n.end(), sort1);
	sort(m.begin(), m.end(), sort1);
	for (auto n_it = n.begin(); n_it != n.end(); n_it++)
	{
		for (auto m_it = m.begin(); m_it != m.end(); m_it++)
		{
			if (*n_it == *m_it)
			{
				size++;
				ans.push_back(*n_it);
				break;
			}
			if (compare(*n_it, *m_it))
				break;
		}
	}
	cout << size << endl;
	for (auto x : ans)
		cout << x << '\n';
}

wkddnjsdlr 3년 전 0

음..

다른 자료구조를 사용해보시는건 어떨까요?

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

문제

문제

출처

ICPC

시간 초과를 어떻게 해야 하나요?

bangbadak 4년 전 0

wkddnjsdlr 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말