백준 2517번 문제
문제
OI 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있으면 남은 거리 동안 앞지르는 것이 가능하다. 이러한 가정 하에서 각 선수는 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다.
각 선수의 평소 실력은 정수로 주어지는데 더 큰 값이 더 좋은 실력을 의미한다. 현재 달리고 있는 선수를 앞에서 부터 표시했을 때 평소 실력이 각각 2, 8, 10, 7, 1, 9, 4, 15라고 하면 각 선수가 얻을 수 있는 최선의 등수는 (같은 순서로) 각각 1, 1, 1, 3, 5, 2, 5, 1이 된다. 예를 들어, 4번째로 달리고 있는 평소 실력이 7인 선수는 그 앞에서 달리고 있는 선수들 중 평소 실력이 2인 선수만 앞지르는 것이 가능하고 평소실력이 8과 10인 선수들은 앞지르는 것이 불가능하므로, 최선의 등수는 3등이 된다.
선수들의 평소 실력을 현재 달리고 있는 순서대로 입력 받아서 각 선수의 최선의 등수를 계산하는 프로그램을 작성하시오.
입력
첫째 줄에는 선수의 수를 의미하는 정수 N이 주어진다. N은 3 이상 500,000 이하이다. 이후 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 이 값들은 각 선수들의 평소 실력을 앞에서 달리고 있는 선수부터 제시한 것이다. 각 정수는 1 이상 1,000,000,000 이하이다. 단, 참가한 선수들의 평소 실력은 모두 다르다.
출력
각 선수의 최선의 등수를 나타내는 정수 N개를 입력에 주어진 선수 순서와 동일한 순서로 한 줄에 하나씩 출력한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#include <stdio.h>
typedef struct Runner{
int position;
int original_index;
}Runner;
Runner pos[500005];
Runner sorted[500005];
int rank[500005];
void merge(int left,int right){
int mid = (left+right)/2;
int l = left, r = mid+1, cur = left;
while(l<=mid && r<=right){
if(pos[l].position<pos[r].position){
rank[pos[r].original_index] -= mid+1-l;
sorted[cur++] = pos[r++];
}
else sorted[cur++] = pos[l++];
}
while(r<=right){
rank[pos[r].original_index] -= mid+1-l;
sorted[cur++] = pos[r++];
}
while(l<=mid) sorted[cur++] = pos[l++];
for(int i = left ; i <= right ; i++) pos[i] = sorted[i];
}
void merge_sort(int left, int right){
int mid = (left+right)/2;
if(left<right){
merge_sort(left,mid);
merge_sort(mid+1,right);
merge(left,right);
}
}
int main(){
int N;
scanf("%d\n",&N);
for(int i = 0 ; i < N ; i++){
int t;
scanf("%d",&t);
Runner r = {t,i};
pos[i] = r;
rank[i] = i+1;
}
merge_sort(0,N-1);
for(int i = 0 ; i < N ; i++) printf("%d\n",rank[i]);
}
|
cs |
merge sort를 이용해서 푸는 문제라는건 알고리즘 멘토링을 통해서 들었었는데
수업을 열심히 듣지 않아 그 후는 어떻게 푸는지 잊어버렸다
복습과정에서 merge sort를 그려가며 어떻게 쓰는지 고민했더니 그래도 금방 풀렸다
merge 하는 과정에서 몇명을 추월 가능한지 생각하면 얼마나 등수를 줄일 수 있는지 알 수 있다
이때 sorting 과정에서 원래의 index를 유지하지 못하니 rank를 저장하기 위해 original index를 따로 저장해주었다
백준 사이트 알고리즘 분류에서는 segment tree로 되어 있던데 아직 segment tree를 자유롭게 사용하기 어려워
그 방법으로는 어떻게 푸는지 모르겠다
segment tree 공부 후 다시 그 방법으로도 풀어보아야겠다
'알고리즘' 카테고리의 다른 글
[C] 2048 (easy) (0) | 2021.03.23 |
---|---|
[C] 구슬 탈출2 (0) | 2021.03.23 |
[C++] 게임 (0) | 2021.02.05 |
[ICPC] Cosmetic Survey (0) | 2020.10.08 |
[ICPC] Rectilinear Regions (0) | 2020.09.30 |