[BaekJoon] 2517.달리기

BeakJoon Online judge

[2517] 달리기

1. Let’s Think

1. 첫번째 Idea

단순하게 i번째 선수의 최대 등수를 얻기 위해 0~i-1번째 선수들의 실력과 i번째 선수의 실력을 비교하여 답을 구해보자.

	vector<int> ans(N);
    for(int i =0; i < N; i++) {
    	int temp = 0;
        for(int j = 0; j < i; j++) {
        	if(ability[i] > ability[j]) {
            	temp++;
            }
        }
        ans[i] = (i + 1) - temp;
    }

위의 코드를 보면 정말 단순하게 문제를 해결할 수 있을 것만 같다. 하지만, 주어진 N의 최대값을 고려한다면 시간 초과가 날 알고리즘임을 알 수 있다. 해당 코드의 Time Complexity : O(N^2) ☞ N의 최댓값 = 500000
∴ 25 * 10^10 즉, 1초를 넘긴다.

2. 두번째 Idea

그렇다면 또 다른 방법에 대해 고민을 해보자. 우선, 실력이 좋을 수록 높은 ability 값을 가지고 있다. 그리고 높은 ability 값을 가지고 있을 수록 앞에 설 가능성이 높다. 그래서 이를 정렬할 때 번거러움이 있을 듯하여 aility에 -1을 곱하여 주자.

	struct Player {
    	int now;
        int ab;
        bool operator< (const Player& a) const {
        	return ab < a.ab;
        } 
    };
    
    int main(void) {
    	......
        for(int i = 0; i < N; i++) {
        	int ab;
            scanf("%d", &ab);
        	players[i] = {i + 1, ab * -1};
        }
        ......
    }

자, 그렇다면 이것을 가지고 어떻게 활용할 수 있을까? 주어진 예제를 가지고 생각해보자. 1. 주어진 예제의 ability에 -1을 곱한다. 2. 각각의 값을 두쌍으로 묶어 정렬한다. 3. 2번에 묶인 쌍을 다시 두개로 합쳐 같은 연산을 반복한다. 4. 모든 묶인 쌍들이 하나의 묶인 쌍이 될때 까지 3번을 반복한다. 5. 각각의 선수들이 추월할 수 있는 앞선 선수들의 수를 알아냈으므로 각각의 선수들의 가능한 최고 등수를 알아 낼 수 있다.

위와 같은 과정들을 보면 merge sort의 과정을 통해 답을 도출하고 있는 것을 알 수 있다.

	vector<int> bestRank;
	void getMerge(vector<Player>& list, int stIndex, int endIndex) {
    	if(stIndex >= endIndex) return;
    	int mid = (stIndex + endIndex) / 2;
    	getMerge(list, stIndex, mid);
    	getMerge(list, mid + 1, endIndex);
 
    	vector<Player> temp(endIndex - stIndex + 1);
    	int idx = 0;
    	int s = stIndex, e = mid + 1;
    	while(s <= mid && e <= endIndex) {
			if(list[s] < list[e]) {
           		temp[idx] = list[s];
            	bestRank[list[s].now - 1] += max(0, s - idx - stIndex);
            	s++;
        	}
        	else {
          		temp[idx] = list[e];
            	bestRank[list[e].now - 1] += max(0, e - idx - stIndex);
            	e++;
        	}
        	idx++;
      	}
    	while(s <= mid) {
        	temp[idx] = list[s];
        	bestRank[list[s].now - 1] += max(0, s - idx - stIndex);
        	s++, idx++;
    	}
    	while(e <= endIndex) {
        	temp[idx] = list[e];
        	bestRank[list[e].now - 1] += max(0, e - idx - stIndex);
        	e++, idx++;
    	}
    	for(int i = 0, j = stIndex; j <= endIndex; i++, j++) {
        	list[j] = temp[i];
    	}
	}

해당 알고리즘은 merge sort와 Time complexity가 동일하므로 O(NlgN) –> 50000 * lg(50000) ≒ 780482
주어진 시간내에 정답 도출이 가능하다.

2. Solve the Problem

#include<stdio.h>
#include<vector>
#include<iostream>
using namespace std;
struct Player {
     int now;
     int ab;
     bool operator< (const Player& a) const {
        	return ab < a.ab;
     } 
};
vector<int> bestRank;
void getMerge(vector<Player>& list, int stIndex, int endIndex) {
   	if(stIndex >= endIndex) return;
    int mid = (stIndex + endIndex) / 2;
    getMerge(list, stIndex, mid);
    getMerge(list, mid + 1, endIndex);
 
    vector<Player> temp(endIndex - stIndex + 1);
    int idx = 0;
    int s = stIndex, e = mid + 1;
    while(s <= mid && e <= endIndex) {
		if(list[s] < list[e]) {
           	temp[idx] = list[s];
            bestRank[list[s].now - 1] += max(0, s - idx - stIndex);
            s++;
        }
        else {
          	temp[idx] = list[e];
            bestRank[list[e].now - 1] += max(0, e - idx - stIndex);
            e++;
        }
        idx++;
      }
    while(s <= mid) {
        temp[idx] = list[s];
        bestRank[list[s].now - 1] += max(0, s - idx - stIndex);
        s++, idx++;
    }
    while(e <= endIndex) {
        temp[idx] = list[e];
        bestRank[list[e].now - 1] += max(0, e - idx - stIndex);
        e++, idx++;
    }
    for(int i = 0, j = stIndex; j <= endIndex; i++, j++) {
        list[j] = temp[i];
    }
}

int main(void) {
    int N;
    scanf("%d", &N);
    vector<Player> players(N);
    for(int i = 0; i < N; i++) {
        int ab;
        scanf("%d", &ab);
        players[i] = {i + 1, -1 * ab};
    }
    bestRank.resize(N, 0);
    getMerge(players, 0, N - 1);
    for(int i = 0; i < N; i++) {
        printf("%d\n", (i + 1 - bestRank[i]));
    }
    return 0;
}

3. End