글 읽기 - 시간초과 질문

heehcs 6년 전 0

퀵소트와 이진탐색을 썼는데요, 시간초과가 납니다.

머지소트를 써야하는 부분인가요?

#include <stdio.h>
#define loop(i,start,stop) for(int i = start; i < stop; i++)

char a[500001][21];
char* result[500001];

int N, M;

int _strlen(char s[]) {
	if(s == NULL) return 0;
	char* p = s;
	while(*p++);
	return p - s - 1;
}

int _strcmp(char s1[], char s2[]) {
	int len1 = _strlen(s1);
	int len2 = _strlen(s2);
	int len = (len1 > len2) ? len1 : len2;
	loop(i,0,len) {
		if(s1[i] < s2[i]) return -1;
		else if(s1[i] > s2[i]) return 1;
	}
	return 0;
}

char* bsearch(char target[], int l , int r) {
	if(l > r) return NULL;
	int mid = l + (r-l)/2;
	if(_strcmp(target,a[mid]) == 0) return a[mid];
	else if(_strcmp(target,a[mid]) < 0) return bsearch(target, l, mid-1);
	else return bsearch(target, mid+1, r);
}

void _strcpy(char s1[], char s2[]) {
	int len = _strlen(s2);
	loop(i,0,len) {
		s1[i] = s2[i];
	}
	s1[len] = '\0';
}

template <typename T>
void _swap(T& e1, T& e2) {
	char temp[21];
	_strcpy(temp,e1);
	_strcpy(e1,e2);
	_strcpy(e2,temp);
}

template <typename T>
int partition(T a[], int l, int r) {
	int len = _strlen(a[l]);
	char* pivot = new char[len+1];
	_strcpy(pivot, a[l]);
	int i = l-1;
	int j = r+1;
	while(true) {
		do i++; while(_strcmp(a[i], pivot) < 0);
		do j--; while(_strcmp(a[j], pivot) > 0);
		if(i<j) _swap(a[i], a[j]);
		else return j;
	}
}

template <typename T>
void quicksort(T a[], int l, int r) {
	if(l >= r) return;
	int s = partition(a,l,r);
	quicksort(a,l,s);
	quicksort(a,s+1,r);
}

int main() {
	scanf("%d %d", &N, &M);
	loop(i,0,N) {
		scanf("%s", a[i]);
	}
	quicksort(a,0,N-1);
	int idx = 0;
	loop(i,0,M) {
		char target[21];
		scanf("%s", target);
		char* res = bsearch(target, 0, N-1);
		if(res != NULL) {
			result[idx++] = res;
		}		
	}
	quicksort(result,0,idx-1);
	loop(i,0,idx) {
		printf("%s\n", result[i]);
	}		
}

topology 6년 전 1

퀵소트와 같은 randomized algorithm은 랜덤성이 있어야만 진가를 발휘합니다. 지금 코드는 pivot을 항상 맨 외쪽 원소로 선택하는데, 이 경우 7 6 5 4 3 2 1과 같은 배열의 정렬에는 O(N^2)의 시간이 걸려 시간초과의 원인이 될 수 있습니다.

피벗을 랜덤으로 선택해 보세요.

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

문제

문제

출처

ICPC

시간초과 질문

heehcs 6년 전 0

topology 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말