C++로 배열에서 가장 강한 k개의 값 찾기

문제 이해하기

숫자 배열 arr와 정수 k가 주어져 있다고 가정해 봅시다. 배열의 중앙값을 m이라 할 때, |arr[i] - m| > |arr[j] - m|이면 arr[i]가 arr[j]보다 강하다(stronger)고 정의합니다. 만약 두 값의 중앙값까지의 거리가 같다면, arr[i] > arr[j]일 때 arr[i]가 더 강한 것으로 간주합니다. 우리의 목표는 배열에서 가장 강한 k개의 값을 찾아 리스트로 반환하는 것입니다.

예를 들어 입력이 arr = [1,2,3,4,5], k = 2라면 출력은 [5, 1]입니다. 중앙값이 3이므로 강함 기준으로 배열을 정렬하면 [5, 1, 4, 2, 3]이 되고, 여기서 가장 강한 두 원소는 [5, 1]입니다. 물론 [1, 5]도 유효한 답입니다. |5 - 3|과 |1 - 3|은 같지만 5가 1보다 크기 때문에 5가 더 강하게 판정됩니다.

접근 방법

이 문제는 다음 단계에 따라 해결할 수 있습니다.

배열 arr를 오름차순으로 정렬합니다.
n := arr의 크기
m := arr[(n - 1) / 2] — 정렬된 배열의 중앙값
쌍(pair)을 저장할 배열 v를 선언합니다.
투 포인터 i := 0, j := n - 1로 초기화합니다.
결과를 저장할 배열 ret을 선언합니다.
k가 0이 될 때까지 아래 과정을 반복합니다.
- x1 := |arr[j] - m|
- x2 := |arr[i] - m|
- x1 >= x2이면 ret 끝에 arr[j]를 추가하고 j를 1 감소시킵니다.
- 그렇지 않으면 ret 끝에 arr[i]를 추가하고 i를 1 증가시킵니다.
ret을 반환합니다.

핵심 아이디어는 배열을 정렬한 후 양쪽 끝에서부터 동시에 탐색하는 것입니다. 정렬된 배열에서 중앙값으로부터 가장 멀리 있는 원소들은 항상 양쪽 끝에 위치하므로, 두 포인터가 가리키는 값을 비교하여 더 강한 쪽을 결과에 차례로 추가하면 됩니다.

C++ 구현 예제

다음 구현을 통해 더 잘 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   int calc(int x, int m){
      return abs(x - m);
   }
   vector<int> getStrongest(vector<int>& arr, int k) {
      sort(arr.begin(), arr.end());
      int n = arr.size();
      int m = arr[(n - 1) / 2];
      vector<pair<int, int> > v;
      int i = 0;
      int j = n - 1;
      vector<int> ret;
      while (k--) {
         int x1 = calc(arr[j], m);
         int x2 = calc(arr[i], m);
         if (x1 >= x2) {
            ret.push_back(arr[j]);
            j--;
         }
         else {
            ret.push_back(arr[i]);
            i++;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,4,5};
   print_vector(ob.getStrongest(v,2));
}

입력

{1,2,3,4,5},2

출력

[5, 1]

복잡도 분석

정렬에 O(n log n), 이후 투 포인터 순회에 O(k)가 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 결과 배열을 제외하면 O(1)로 매우 효율적입니다.