[Programmers] #120880 - 특이한 정렬 [Java][C++][Python]

문제 링크

---

1. 아이디어

정수 배열 numlist와 정수 n에 대해 numlist의 원소를 n에 가까운 순서로, 거리가 같으면 큰 수가 앞에 오도록 배치하는 문제로 언어별 정렬을 활용하면 된다.

---

2. 복잡도

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

($N$ = numlist의 길이. Java는 [거리, 값] 쌍을 담는 2차원 배열을 새로 만들어 반환하므로 공간 $O(N)$)

---

3. 코드

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

import java.util.*;

class Solution {
    public int[] solution(int[] numlist, int n) {
        int len = numlist.length;
        int[][] arr = new int[len][2];
        for (int i = 0; i < len; i++) {
            arr[i][0] = Math.abs(n - numlist[i]);
            arr[i][1] = numlist[i];
        }
        Arrays.sort(arr, (o1, o2) -> {
            if (o1[0] != o2[0]) return Integer.compare(o1[0], o2[0]);
            return Integer.compare(o2[1], o1[1]);
        });

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

        return ans;
    }
}

2차원 배열 arr을 두고 0번 열에는 n과의 거리를, 1번 열에는 원소를 넣었다. 정렬은 거리가 가까운 순서로, 거리가 같으면 원소가 큰 순서로 정렬하면 된다.

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

vector<int> solution(vector<int> numlist, int n) {
    sort(numlist.begin(), numlist.end(), [&](int a, int b) {
        int da = abs(n - a), db = abs(n - b);
        if (da != db) return da < db;
        return a > b;
    });

    return numlist;
}

n과의 거리를 나타내는 da, db를 계산 후 이를 활용했다.

def solution(numlist, n):
    numlist.sort(key=lambda x: (abs(n - x), -x))
    return numlist

---