[BOJ] 백준 2517번 달리기 자바(java) 풀이 (merge sort 풀이, segment tree 풀이)

BOJ 2517번 달리기 문제 자바(java) 풀이

• 랭크 : 플레티넘5
• 백준 2517번 달리기
  
  
  

문제 정리

1. 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 앞지르는 것은 불가능하다.
2. 평소 실력이 자기보다 좋지 않은 선수가 앞에 달리고 있다면 남은 거리 동안 앞지르는 것이 가능하다.
3. 자신이 앞으로 얻을 수 있는 최선의 등수를 알 수 있다.
4. 각 선수의 평소 실력이 주어진다.(클 수록 실력 上)
5. 선수의 평소 실력이 앞에서 부터 주어질때 각 선수의 최선의 등수를 계산하여라.
   
   
   

문제 풀이

자신보다 앞에 있는 사람중 실력이 더 낮은 사람들의 수를 구하면 됩니다.
다음 두 가지 방법으로 풀 수 있습니다.

• merge sort 풀이

1. 선수들의 실력과 index를 Num 객체아 담아 저장합니다.
2. merge sort를 이용해 내림차순으로 정렬합니다.
   왼쪽과 오른쪽으로 배열을 인덱스 기준으로 나눠갑니다.
   내림 차순이므로 왼쪽이 크다면 왼쪽의 수를 sorted배열에 먼저 넣습니다.
   오른쪽 수가 더 큰 경우 내림차순 이므로 그 뒤의 모든 수들 도 작기 때문에
   mid(전체 개수)-leftIdx(현재 leftIdx)가 뒤에 있는 숫자의 개수(leftIdx 포함)가 됩니다.
   그리고 남은 수 들을 sorted 배열에 넣어 줍니다.
   ```
   예를 들어 왼쪽 (6,3,2) 오른쪽 (5,4,1)이라고 가정하겠습니다.
   왼쪽과 오른쪽을 비교해 나갑니다.
3. 6와 5 비교: 4 앞에 있는 수인 6는 6보다 크기 때문에 작은 개수로 count하지 않습니다.
4. 3와 6 비교: 6 앞에 있는 수 3은 6보다 작습니다. 내림차순 이기 때문에 왼쪽의 3 뒤에 있는 수 모두 5보다 작을 것입니다. 즉 5 앞에 있는 5보다 작은 수는 왼쪽 크기(3) - 3의 index(1) = 2 입니다.
   이것이 코드 상에서 mid-leftIdx 입니다.
   입력으로 주어진 순서에서 앞에 있는 작은 수 개수 만큼 땡겨지므로 빼줍니다.
   ```

• segment tree 풀이

1. list에 입력으로 주어진 순서 index와 실력을 Num객체에 저장합니다.
2. list에 있는 값들을 실력을 기준으로 오름차순 정렬합니다.
3. segment tree의 base 값을 계산합니다.
4. 작은 숫자의 index부터 꺼냅니다. 그 앞의 범위(idx-1)에 1이 몇개 있는지 셉니다. 그 개수가 앞에 놓인 작은 숫자의 개수입니다.
5. 해당 index에 1을 놓습니다.
6. 작은 숫자 부터 놓기 때문에 앞에 1이 있다면 먼저 놓인 작은 숫자의 개수가 됩니다.
   
   
   

백준 달리기 merge sort 풀이

백준 달리기 segment tree 풀이