[Programmers] #120835 - 진료순서 정하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

emergency 값이 클수록 응급도가 높으므로, 값 기준 내림차순으로 정렬했을 때의 순위가 곧 진료 순서가 된다. 값 자체를 정렬하면 원래 인덱스 정보를 잃으므로, 인덱스 배열을 만들어 emergency 값 기준 내림차순으로 정렬한 뒤, 정렬된 순서대로 1부터 순위를 매겨 각 인덱스가 원래 있던 위치에 그 순위를 기록한다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \log N)$	$O(N)$

$N$은 emergency의 길이다.

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public int[] solution(int[] emergency) {
        int n = emergency.length;

        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) {
            idx[i] = i;
        }
        Arrays.sort(idx, (o1, o2) -> Integer.compare(emergency[o2], emergency[o1]));

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[idx[i]] = i + 1;
        }

        return ans;
    }
}

Arrays.sort는 기본형 배열(int[])에는 커스텀 Comparator를 적용하는 오버로드가 없어서, 인덱스를 박싱된 Integer[]에 담아 정렬해야 한다.

#include <bits/stdc++.h>
using namespace std;

vector<int> solution(vector<int> emergency) {
    int n = emergency.size();

    vector<int> idx(n);
    for (int i = 0; i < n; i++) idx[i] = i;

    sort(idx.begin(), idx.end(), [&](int a, int b) {
        return emergency[a] > emergency[b];
    });

    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        ans[idx[i]] = i + 1;
    }

    return ans;
}

def solution(emergency):
    n = len(emergency)
    idx = sorted(range(n), key=lambda i: emergency[i], reverse=True)

    ans = [0] * n
    for rank, i in enumerate(idx, start=1):
        ans[i] = rank

    return ans

enumerate(idx, start=1)로 정렬된 인덱스를 순회하면서 1부터 시작하는 순위를 별도 변수 없이 바로 얻을 수 있다.

---