동점자를 생각한 등수

문제 내용

학생들의 성적이 배열로 주어집니다. 각 학생의 성적에 대한 등수를 계산하고, 이를 배열로 반환해야 합니다. 등수는 성적이 높은 학생부터 1등으로 시작해서 낮은 학생 순으로 계산됩니다.

만약 두 명 이상의 학생이 동일한 성적을 가지고 있다면, 그들은 동등하게 같은 등수를 가집니다. 이 경우, 동점자들 다음의 등수는 동점자 수만큼 건너뛰게 됩니다. 예를 들어, 두 학생이 1등이라면, 다음 학생은 3등이 됩니다.

성적 배열을 입력으로 받아, 위의 규칙에 따라 각 학생의 등수를 배열로 반환하는 함수를 작성해야 합니다.

풀이방법

처음 생각한 풀이 방법: 성적을 정렬한 이후에 원본 배열을 돌면서 각 점수에 대한 indexOf 구하면 정렬하면서 동점자들은 뒤에 있기 때문 문제에서 구하는 등수를 구할 수 있을 거라고 생각했다. 구현한 후에 채점을 진행하니까 정확도는 100%였는데 효율성에서 100%가 나오지 못했다. 이유를 찾아 보니 indexOf 함수의 복잡도가 O(n)인데 배열을 돌면서 진행하기 때문 O(n^2)이 되버리기 때문이다.

효율성까지 고려한 방법: 등수를 구하려면 정렬은 필수 인것 같다. 그러면 indexOf를 없애야 하는 것 같다. 이를 위해 배열을 map으로 바꾸고 점수에 대해서 정렬을 하되, 원래 원본 배열의 index도 같이 가지고 있게 한다. 그리고 정렬된 map을 돌면서 각 객체가 들고있는 index의 value 값을 이용해 원본배열의 등수들을 채워가는 것이다.

풀이 1

function solution(gradeArr) {
    const answer = new Array(gradeArr.length);
    const gradeInfo = [...gradeArr].sort((b,a) => b - a); // 함수를 넣어주지 않으면 문자열 기준 정렬이 발생함
    gradeArr.forEach((grade, index) => {
        answer[index] = gradeInfo.indexOf(grade);
    });
    return answer;
}

풀이 2

function solution(gradeArr) {
    const answer = new Array(gradeArr.length);
    const gradeInfo = [...gradeArr].map((grade, index) => ({grade, index})).sort((a, b) => 
        b.grade - a.grade || a.index - b.index
    );

    let sameRank = 0;
    let curRank = 1;
    for(let i = 0 ; i < gradeArr.length ; i++) {
        if (i > 0 && gradeInfo[i].grade < gradeInfo[i - 1].grade) {
            curRank += sameRank;
            sameRank = 0;
        }
        answer[gradeInfo[i].index] = curRank;
        sameRank++;
    }
    return answer;
}