글 읽기 - 1377번 시간초과와 관련해서 궁금한 점이 있어서 질문드립니다.

newsanghoon 3년 전 0

안녕하세요! 이 문제를 풀던 중 입력 개수가 500000개이니 nlogn한 stable한 sort를 구현해야겠다고 생각이 들었습니다. 그래서 mergeSort를 구현하여 문제를 해결하려고 했는데 자꾸 시간초과가 나오네요. 혹시 제가 구현한 mergeSort 중에 어느 부분이 비효율적이라서 시간초과가 나오는 걸까요?

감사합니다.

#include <cstdio>
#include <vector>
#include <stdlib.h>
using namespace std;

pair<int, int> arr[500002];

void mergeSort(int start, int end);
void merge(int start, int mid, int end);

int main(){
	int N;
	int number;
	scanf("%d", &N);

	for(int i = 0; i < N; i++){
		scanf("%d", &number);
		arr[i] = make_pair(number, i);
	}
	mergeSort(0, N-1);
	
	int maxNum = 0;

	for(int i = 0; i < N; i++){
		if(arr[i].second - i > maxNum)
			maxNum = arr[i].second - i;
	}

	printf("%d", maxNum+1);
}	



void mergeSort(int start, int end){
	if(start < end){
		int mid = (start + end)/2;
		mergeSort(start, mid);
		mergeSort(mid+1, end);
		merge(start, mid, end);
	}
}

void merge(int start, int mid, int end){
	pair<int, int> temp[500002];
	int part1 = start, index = start, part2 = mid+1;

	for(int i = start; i <= end; i++)
		temp[i] = arr[i];

	while(part1 <= mid && part2 <= end){
		if(temp[part1].first > temp[part2].first){
			arr[index] = temp[part2];
			part2++;
		}else{
			arr[index] = temp[part1];
			part1++;
		}
		index++;
	}

	for(int i = 0; i <= mid - part1; i++){
		arr[index + i] = temp[part1 + i];
	}
}

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

문제

문제

출처

ICPC

1377번 시간초과와 관련해서 궁금한 점이 있어서 질문드립니다.

newsanghoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말