글 읽기 - [c++]시간초과가 뜨는데 어떤부분에서 문제인가요? 고수님들 도와주세요.

jwon2 5년 전 0

거의 2년가까이 손놓고 있다가

군대에서 짬짬히 연등하면서 공부하다보니 심리적여유가 없네요ㅜㅜ

오늘 시간도 다 끝나가서 다음주에야 다시 잡을 수 있는데 그러기엔 너무찜찜해서ㅜㅜ

정렬을 sort()함수 쓰는게 양심에 찔리지만... 요것도 O(nlogn)으로 알고 있는데 왜 시간초과가 뜰까요?

정확히 어떤부분에서 시간이 지연되는지 고수님들의 도움을 구합니다.

#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;

#define For(i,n) for(int i=0; i< (n) ; i++) 
struct word {
		string str;
		short length;
};
bool cmp(word a,word b){
	if(a.length==b.length){
		for(int i=0;i<a.length;i++){
			if(a.str[i]!=b.str[i])
				return a.str[i]<b.str[i];
		}
	}
	else 
		return a.length<b.length;
}
int main(int argc, char* argv[]) {
	
	cin.tie(NULL);
	cout.sync_with_stdio(false);
	
	int N;
	cin >> N;
	
	
	word wordlist[20010];
	
	For(i,N){
		cin >> wordlist[i].str;
		wordlist[i].length = wordlist[i].str.length();
	}
	
	sort(wordlist,wordlist+N,cmp);
	
	For(i,N){
		if(i>0){
			if(wordlist[i].str!=wordlist[i-1].str)
				cout << wordlist[i].str << "\n";
		}
		else
			cout << wordlist[i].str << "\n";
	}
	return 0;
} 