백준 2517번 : 달리기

달리기 

*일단 나는 머지소트로 했는데 [https://justicehui.github.io/koi/2019/03/03/BOJ2517/] 여기보면 세그먼트 트리도 된다 함 아직 안해봤다 난 그리고 비슷한 문제로 [https://www.acmicpc.net/problem/10090]

 

앞에 자기보다 큰게 몇개 있느냐는 문제이다.

2 8 10 7 1 9 4 15

최악의 시간 복잡도로라도 생각하면 그냥 하나씩 고르고 그 앞을 쭉 보면서 자기보다 큰게 몇개인지 세어보면 된다.

근데 그러면 O(n^2)이겠지....

 

음 이런식으로 고르고 오름차순 정렬이되 도록 올려주면 결국 되긴한다. 근데 문제가 그러면 효율적으로 올려서 정렬되는게 아니라는거. 여기서 방법으로 머지소트 방식을 떠올릴 수 있겠다.

 

근데 구현했는데 틀렸다.....아 머지소트 구현도 어렵고, 어떻게 몇번 올라왔는지 갯수 세는 것도 어렵다. 기존 배열을 유지해야 마지막에 출력하기 용이한데, 나는 정렬해버리니까 어떻게 기존 배열대로 출력할지 모르겠다..... 

 

<https://eine.tistory.com/entry/%EB%B0%B1%EC%A4%80-2517-%EB%8B%AC%EB%A6%AC%EA%B8%B0-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4>

 

여기를 참고했다.

 

for (int i=1; i <= n; i++) 
{ 
	scanf("%d", &A[i].first);
    A[i].second = i;
    ans[i] = i;
}

 

결국 ans배열은 답을 저장한다. 그러면 정렬하는 대상 배열이 자기 값이랑 인덱스를 알아야 올바른 ans 배열의 위치에다가 정렬중에 몇번 앞으로 가는지 저장할 수 있다.

 

마았따. 2시간정도 헤맸는데, 헤맨 부분이 그 머지소트할때 변수가 생각보다 많이 필요했다. 쓸고 지나가는 변수도 st, mid로 두개 있어야되는데 초기 st랑 mid를 고정해서 저장해 놓아야 범위 확인 할 수 있는 변수도 있었다;;

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<malloc.h>
#include<vector>
#include<stdlib.h>
#include<string.h>
#include<string>
#define NUM 500001

using namespace std;

struct vw {
	int val, index;
};

int ans[NUM] = { 0 };
vw arr[NUM];
vw brr[NUM];
int N;



void swap(int*a, int*b) {
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
}

void partition(int st, int end, vw *arr) {
	int fixed_st = st;
	
	int mid = (st + end) / 2+1;
	int fixed_mid = mid;

	int ind = 0;


	while (st < fixed_mid && mid <= end) {
		if (arr[st].val > arr[mid].val) {
			ans[arr[mid].index] += mid - ind - fixed_st;
			brr[ind++] = arr[mid++];
		}
		else {
			brr[ind++] = arr[st++];
		}
	}
	while (st < fixed_mid) {
		brr[ind++] = arr[st++];
	}
	while (mid <= end) {
		ans[arr[mid].index] += mid - ind - fixed_st;
		brr[ind++] = arr[mid++];
	}

	for (int i = fixed_st; i <= end; i++) {
		arr[i] = brr[i - fixed_st];

	}

	return;
}

void merge(int st, int end, vw *arr) {
	int mid = (st + end) / 2;
	
	//if (st == end) return;

	if (st < end) {
		merge(st, mid, arr);
		merge(mid + 1, end, arr);
		partition(st, end, arr);
	}
}





int main() {

	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);


	freopen("input.txt", "r", stdin);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i].val;
		arr[i].index = i;
	}

	merge(0, N - 1, arr);

	for (int i = 0; i < N; i++) {
		cout << ans[i] + 1 << "\n";
	}

	return 0;
}