[알고리즘] 달리기(Merge Sort를 활용)

자신보다 앞에서 달리고 있는 사람들 중

자신보다 실력이 낮은 사람은 몇명인가?

 

- 입력 : 크기 N인 배열 A가 주어진다.

A[1]은 현재 1등인 사람의 평소실력,  

A[2]은 현재 2등인 사람의 평소실력을 나타낸다.

 

문제 : 어떤 사람 A[i]보다 실력이 낮은 사람이,

A[1] ~ A[i-1]에 몇명이나 있는가?

 

ex)

1등 3

2등 4

3등 1

4등 2

5등 6

6등 8

7등 5

8등 9

9등 10

10등 7

 

Merge Sort를 이용한 접근방법.

잘게 쪼개어서, 합쳐지는 과정에 현재 숫자가 왼쪽에 N개보다 크면 N개를 저장.

 

 

이 사진과 같이 표현이 가능하다.

작은 숫자는 오른쪽에서 왼쪽으로 넘어가면서, 자신보다 큰 숫자를 만난경우 해주는 count 이다.

 

이렇게 한다면, 결과를 도출해낼 수 있다.