[프로그래머스][C++] 특이한 정렬

특이한 정렬

문제 링크

특이한 정렬

분석

n과의 절댓값 거리가 작은 수부터 순차적으로 정렬합니다.
거리가 같다면, 큰 수를 내림차순으로 배치합니다.

이 문제는 정렬 함수를 사용하고, 비교함수를 오버라이딩하여 풀어낼 수 있습니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<int> numlist, int n) {
    
    // 사용자 정의 함수를 람다로 지정
    sort(numlist.begin(), numlist.end(), [n](int a, int b)
         {
            // a와 n의 거리 계산
             int distanceA = abs(a - n);

             // b와 n의 거리 계산
             int distanceB = abs(b - n);
             
             // 거리가 다를 경우 더 가까운 수가 먼저 오도록 정렬
             if (distanceA != distanceB)
             {
                 return distanceA < distanceB;
             }
             
             // 거리가 같을 경우 더 큰 수가 먼저 오도록 내림차순 정렬
             return a > b;
         });
    
    return numlist;
}

성능 요약

시간 복잡도는 $O(n \ log \ n)$입니다.

• 정렬 함수 $O(n \ log \ n)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.02ms, 4.21MB)
테스트 2 〉 통과 (0.03ms, 4.21MB)
테스트 3 〉 통과 (0.02ms, 3.68MB)
테스트 4 〉 통과 (0.02ms, 4.2MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 4.14MB)
테스트 7 〉 통과 (0.01ms, 4.21MB)