글 읽기 - std::sort로는 시간 초과가 나나요?

knight7024 6년 전 0

벡터 페어를 문자열로 정렬해서 이진 검색하는 소스입니다.

cin과 cout이 시간 초과 난대서 scanf, printf로 바꾸었습니다.

16%에서 시간 초과가 나는데 다른 분들은 map 쓰셨더라구요.

벡터 std::sort 로는 못 푸나요?

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cctype>
using namespace std;
int strBinaryS(vector<pair<string, int>> arr, int size, string findItem)
{
	int front = 0, back = size - 1, middle;
	while (front <= back)
	{
		middle = front + (back - front) / 2;
		if (arr[middle].first.compare(findItem) > 0) back = middle - 1;
		else if (arr[middle].first.compare(findItem) < 0) front = middle + 1;
		else break;
	}
	return middle;
}
int main()
{
	int N, M;
	char tempChar[21];
	string tempStr;
	vector<pair<string, int>> pokemon; vector<string> index;
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++) scanf("%s", tempChar), tempStr = tempChar, pokemon.push_back(pair<string, int>(tempStr, i)), index.push_back(tempStr);
	sort(pokemon.begin(), pokemon.end());
	while (M--)
	{
		scanf("%s", tempChar), tempStr = tempChar;
		if (isalpha(tempStr[0])) printf("%d\n", pokemon[strBinaryS(pokemon, N, tempStr)].second + 1);
		else printf("%s\n", index[stoi(tempStr) - 1].c_str());
	}
	return 0;
}

chogahui05 6년 전 2

이렇게 고쳐보세유

int strBinaryS(vector<pair<string, int>> &arr, int size, string findItem)
{
    ...
}

knight7024 6년 전 0

앗 맞았어요

혹시 이유가 뭔지 알려주실 수 있나요??

chogahui05 6년 전 2

벡터를 고대로 넘기는 것 = 크기가 어마어마한 것을 통째로 넘기는 것 이라고 생각하심 편할 거 같아요.

일단 여기까지만 답변드리고 나머지는 더 찾아볼게요.

아래 프로그램을 실행하면 결과는 1이 나옵니다.

아. 수족관 어렵네요.

#include <stdio.h>
#include <vector>
using namespace std;
void foo(vector <int> v);
int main(void)
{
    vector <int> v; v.push_back(1);
    foo(v);
    for(int i=0;i<v.size();i++)
        printf("%d ",v[i]);
    return 0;
}
void foo(vector <int> v)
{
    v.push_back(2);
}

chogahui05 6년 전 1

제가 봤을 때는 이런 거 같습니다. 정확하진 않겠지만..

일단 위 예제에서는 vector <int> v를 넘겨버렸습니다.

그리고 foo에서 받죠. callee의 인자가 v니까유.

foo함수의 v = main 함수의 v가 됩니다. 벡터의 대입 연산이죠.

이건 연산자 override 되어있습니다.

이 사이트를 보세요.

http://www.cplusplus.com/refer...

분명한 건 복잡도가 size에 비례한다고 되어 있습니다. 즉 할당한다는 소리겠지요.

chogahui05 6년 전 1

그런데 &로 줘버리면. &는 별명입니다.

int chogahui=9;

int &chokw = chogahui; 라고 한다면 chokw의 별명은 chogahui가 되는 거죠.

그러니까

저를 chokw로 부르던.. chogahui로 부르던. 저를 부르는 건 똑같잖아요. 그런 것이랑 마찬가지라 생각하심 됩니다.

어찌 되었던, callee의 v는 main에 있는 벡터 v의 별명이므로, 사실상 같은 공간을 가리키고 있게 됩니다.

따라서, 추가적인 할당이 안 일어나겠지요.

knight7024 6년 전 0

아 오버라이드 연산자 들어본 거 같습니다.

상세한 설명 감사합니다!!! 이렇게 또 하나 배워갑니다 ㅎㅎㅎ

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

문제

문제

출처

ICPC

std::sort로는 시간 초과가 나나요?

knight7024 6년 전 0

chogahui05 6년 전 2

knight7024 6년 전 0

chogahui05 6년 전 2

chogahui05 6년 전 1

chogahui05 6년 전 1

knight7024 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말