글 읽기 - 한 70% 즈음에서 시간초과가 납니다.

wltjd666 2년 전 0

compare 함수에서 string에 복사하는 것 때문에 더 걸리는 것 같은데

어디가 문제인지 정확하게 잘 모르겠습니다. 시간을 더 단축할 수 있는 방법이 있을까요?

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

string filenames[200'001];
unordered_map<string, bool> extensions;

const int MaxFileNameLength = 10;

string getFilename(const string s)
{
	string ret = "";
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '.')
		{
			break;
		}
        ret += s[i];
	}

	return ret;
}

string getExtension(const string& s)
{
	string ret = "";
    int index = s.size();
	for (int i = 0; i < s.size(); i++)
	{
        if (i > index)
        {
            ret += s[i];
            continue;
        }
		if (s[i] == '.')
		{
			index = i;
		}
	}

	return ret;
}

bool compare(const string& a, const string& b)
{
    string a_name = getFilename(a);
	string b_name = getFilename(b);

    if (a_name < b_name)
        return true;
    else if (a_name == b_name)
    {
        string a_ext = getExtension(a);
        string b_ext = getExtension(b);

        if (extensions[a_ext] != extensions[b_ext])
            return extensions[a_ext];
        else
        {
            if (a_ext < b_ext)
                return true;
            else
                return false;
        }
    }
    else
        return false;
}

int main()
{
	int n, m;
	cin >> n >> m;

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

	for (int i = 0; i < m; i++)
	{
		string s;
		cin >> s;
		extensions[s] = true;
	}

	sort(begin(filenames), begin(filenames) + n, compare);

	for (int i = 0; i < n; i++)
		cout << filenames[i] << "\n";
}