알고리즘 :: 마라톤, Merge Sort [푸는중]

알고리즘 공부하며 배운내용

 

 

마라톤 경기

트랙에 N명이 달리고 있다.

모든 선수는 각자 실력인 S가 있고 자신보다 실력이 낮은 사람을 추월이 가능하다

 

예를 들면 선두에 달리는 선수부터 나타내면 이렇다

1 3 2 4 4 3 5

여기서 실력이 3인 두 번째 선수는, 실력이 1인 첫 번째 선수를 앞질러 1등을 할 수 있다.

하지만 세 번째 선수는 아무리 빨리가도 2등이 최고다

 

이럴 때, 각 선수가 기록하는 최대 등수를 출력을 해보자

 

 

들어오는 값

실력 S가 선두부터 차례대로 입력된다.

예)

1 3 2 4 4 3 5

 

 

구할 값

최대 등수를 입력과 같은 순서로 출력

예)

1 1 2 1 2 4 1

 

 

생각

바로 생각났던 방법은 for문으로 두 번째부터 앞의 번호와 비교하는 방법

 

 

핵심 포인트

병합 정렬(Merge Sort)을 이용하면 빠르다고 한다.

병합 정렬 자세한 설명

링크 1 => Code Playground

링크 2 => 춤추는 개발자

링크 3 => ZeroCho Blog

 

 

코드 [미완료]

못 풀고 시간을 너무 써서 다음에 해보는걸로.

병합 정렬(Merge Sort)을 만드는 것까지는 됐는데,

원래 순서대로 각 선수의 최대 등수를 표현을 못했다.

원래 순서를 기억하는건 괜찮은데, 이걸 써먹어서,

병합 정렬에서 오른쪽 부분에 밑의 조건대로 더해줘서 저장을 해야되는데 감을 못잡고 있다.

조건은 모두 1에서 시작하고 밑의 조건에 따라 최대 등수가 정해진다

조건 1. 오른쪽 원소가 왼쪽 앞으로 갈 때 왼쪽 배열.slice(왼쪽 인덱스) 만큼 더해준다.

조건 2. 배교하는 값이 같으면 오른쪽 녀석에 1을 더해준다.

 

let fs = require('fs')
let input = fs.readFileSync('marathon.txt').toString().split(' ')
let rank = input.map(Number)
let runners = {}

for(let i = 0; i < input.length; i ++) {
    runners[i] = +input[i]
}
console.log(runners);

function mergeSort(arr) {
    if(arr.length < 2) {
        return arr.map(Number)
    }
    let mid = Math.floor(arr.length / 2)
    
    let a_l = arr.slice(0, mid)
    let a_r = arr.slice(mid)
    return merge(mergeSort(a_l), mergeSort(a_r))
}

function merge(a_l, a_r) {
    let result = []
    let l_index = 0
    let r_index = 0

    while(l_index < a_l.length && r_index < a_r.length) {
        if(a_l[l_index] <= a_r[r_index]) {
            result.push(a_l[l_index])
            l_index++
        }
        else {
            result.push(a_r[r_index])
            r_index++
        }
    }   
    return result.concat(a_l.slice(l_index), a_r.slice(r_index))
}

console.log(mergeSort(input))