인프런 커뮤니티 질문&답변

안녕하세요^^

백준 기준으로 예를 들어 드리겠습니다. 백준에 2517번 "달리기"라는 문제가 있는데 제한시간이 1초(1000ms)인 문제입니다. 이 문제 n제한이 50만입니다. 저는 이 문제를 병합정렬을 이용해 O(nlogn)으로 풀었는데, 채점한 결과가 아래와 같이 170ms(0.17초)나왔습니다. O(nlogn)은 O(n^2)보다는 O(n)에 매우 가까운 복잡도라 생각하면 됩니다. 아래는 "달리기"문제 병합정렬로 푼 소스코드입니다.

#include<bits/stdc++.h>
using namespace std;
struct Data{
	int idx, speed, rank;	
};

vector<Data> a(500000), tmp(500000);
int res[500000];

void divide(int lt, int rt){
	int mid;
	int p1, p2, p3;
	if(lt<rt){
		mid=(lt+rt)/2;
		divide(lt, mid);
		divide(mid+1, rt);
		p1=lt;
		p2=mid+1;
		p3=lt;
		while(p1<=mid && p2<=rt){
			if(a[p1].speed<a[p2].speed) tmp[p3++]=a[p1++];
			else{
				tmp[p3]=a[p2++];
				tmp[p3].rank+=mid-p1+1;
				p3++;
			}
		}
		while(p1<=mid) tmp[p3++]=a[p1++];
		while(p2<=rt) tmp[p3++]=a[p2++];
		
		for(int i=lt; i<=rt; i++){
			a[i]=tmp[i];
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	//freopen("input.txt", "rt", stdin);
	int n;
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>a[i].speed;
		a[i].idx=i;
		a[i].rank=0;	
	} 
	divide(0, n-1);
	for(int i=0; i<n; i++){
		res[a[i].idx]=a[i].rank+1;
	}
	for(int i=0; i<n; i++){
		cout<<res[i]<<"\n";
	}
	return 0;
}