글 읽기 - 자꾸 9%에서 시간초과가 뜨네요..

jmingrove21 4년 전 0

질문에 있는 반례 모두 넣어봤는데 답은 정확히 나옵니다.

길이로 정렬, 사전순 정렬시 퀵소트를 구현했는데요.

자꾸 시간초과가 뜨네요. 제가 놓친 부분이 있을까요...ㅜ

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> arr;

void check_length(int left, int right){
	int pivot = left;
	int j = pivot;
	int i = left + 1;

	if (left < right){
		for (; i <= right; i++){
			if (arr[i].size() < arr[pivot].size()){
				j++;
				string temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
		string temp1 = arr[left];
		arr[left] = arr[j];
		arr[j] = temp1;
		pivot = j;

		check_length(left, pivot - 1);
		check_length(pivot+1, right);

	}


}
void check_alpa(int left, int right){
	int pivot = left;
	int j = pivot;
	int i = left + 1;

	if (left < right){
		for (; i <= right; i++){
			if (arr[i].size() == arr[pivot].size()){
				string first = arr[i];
				string second = arr[pivot];
				if (first.compare(second)>0){
					break;
				}
				else if (first.compare(second) < 0){
					j++;
					string temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}

			}
		}
		string temp1 = arr[left];
		arr[left] = arr[j];
		arr[j] = temp1;
		pivot = j;

		check_alpa(left, pivot - 1);
		check_alpa(pivot + 1, right);

	}
	
}
int main(void){
	int number;
	cin >> number;
	arr.resize(number);
	arr.clear();
	for (int i = 0; i < number; i++){
		string str;
		cin>> str;
		arr.push_back(str);
	}
	sort(arr.begin(), arr.end());
	arr.erase(unique(arr.begin(), arr.end()), arr.end());
	check_length(0,arr.size()-1);
	check_alpa(0, arr.size() - 1);
	for (int i = 0; i < arr.size(); i++){
		printf("%s\n", arr[i].c_str());
	}
	return 0;
}

wg7221 4년 전 0

저도 퀵소트 구현해서 했는데 시간 초과났어요.

아마 퀵소트가 중복값이 많으면 성능이 안좋아져서 시간초과가 나는것 같아요.

저는 중복제거를 문자열 입력받는 단계에서 해쉬테이블로 실행하고 정렬하니까 시간초과 해결됐어요.

한번 중복제거하고 정렬해 보세요.

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

문제

문제

출처

ICPC

자꾸 9%에서 시간초과가 뜨네요..

jmingrove21 4년 전 0

wg7221 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말