[Codility] Array Inversion Count

 

[Codility] Array Inversion Count

https://app.codility.com/programmers/trainings/4/array_inversion_count/start/

Codility

---

 

해결전략

 

정렬 Sorting

 

※ 중요!

• QuickSort를 사용하면 안 된다!!

---

 

처음 시도한 코드 - 선택 정렬 (시간 초과)

 

 

#include <algorithm>
using namespace std;

int solution(vector<int> &A) {
    int answer = 0;
    int n = A.size();

    for(int i = 0; i < n-1; i++){
        int idx = i;
        for(int j = i+1; j < n; j++){
            if(A[idx] > A[j]) answer++;
        }
    }

    answer = (answer > 1000000000) ? -1 : answer;

    return answer;
}

 

---

 

정답코드 -  MergeSort 병합정렬

 

#include <algorithm>
using namespace std;

int answer;

int Merge(vector<int>& v, int left, int mid, int right) 
{
  int i = left;
  int j = mid;
  int k = 0;

  int invCount = 0;
  int temp[(right - left + 1)];
 
  while ((i < mid) && (j <= right)) 
  {
    if (v[i] <= v[j]) {
      temp[k] = v[i];
      ++k;
      ++i;
    } 
    else {
      temp[k] = v[j];
      invCount += (mid - i);
      ++k;
      ++j;
    }
  }
 
  while (i < mid) {
    temp[k] = v[i];
    ++k;
    ++i;
  }
 
  while (j <= right) {
    temp[k] = v[j];
    ++k;
    ++j;
  }
 
  for (i = left, k = 0; i <= right; i++, k++) {
    v[i] = temp[k];
  }
 
  return invCount;
}

int MergeSort(vector<int>& v, int left, int right) 
{
  int cnt = 0;
 
  if (left < right) 
  {
    int mid = (right + left) / 2;

    cnt = MergeSort(v, left, mid);
    cnt += MergeSort(v, mid + 1, right);
    cnt += Merge(v, left, mid + 1, right);
  }

  return cnt > 1000000000 ? -1 : cnt; // 문제조건: 100000000초과일 때 -1 리턴
}

int solution(vector<int> &A) {
    
    return MergeSort(A, 0, A.size()-1);
}

 

 

 

 

#include <algorithm> 
using namespace std; 

int answer; // 결과값을 저장할 전역 변수입니다.

// Merge 함수는 두 개의 정렬된 부분 배열을 병합하고, 역순 정렬 쌍의 수를 반환합니다.
int Merge(vector<int>& v, int left, int mid, int right) 
{
  int i = left; // 왼쪽 부분 배열의 시작 인덱스입니다.
  int j = mid; // 오른쪽 부분 배열의 시작 인덱스입니다.
  int k = 0; // 임시 배열의 인덱스입니다.

  int invCount = 0; // 역순 정렬 쌍의 수를 저장하는 변수입니다.
  int temp[(right - left + 1)]; // 병합된 결과를 저장할 임시 배열입니다.
 
  // 왼쪽 부분 배열과 오른쪽 부분 배열을 모두 훑을 때까지 반복합니다.
  while ((i < mid) && (j <= right)) 
  {
    // 왼쪽 요소가 오른쪽 요소보다 작거나 같으면 왼쪽 요소를 임시 배열에 추가합니다.
    if (v[i] <= v[j]) {
      temp[k] = v[i];
      ++k;
      ++i;
    } 
    // 왼쪽 요소가 오른쪽 요소보다 크면 오른쪽 요소를 임시 배열에 추가하고, 역순 정렬 쌍의 수를 갱신합니다.
    else {
      temp[k] = v[j];
      invCount += (mid - i);
      ++k;
      ++j;
    }
  }
 
  // 왼쪽 부분 배열의 남은 요소들을 임시 배열에 추가합니다.
  while (i < mid) {
    temp[k] = v[i];
    ++k;
    ++i;
  }
 
  // 오른쪽 부분 배열의 남은 요소들을 임시 배열에 추가합니다.
  while (j <= right) {
    temp[k] = v[j];
    ++k;
    ++j;
  }
 
  // 임시 배열의 요소들을 원본 배열에 복사합니다.
  for (i = left, k = 0; i <= right; i++, k++) {
    v[i] = temp[k];
  }
 
  return invCount; // 역순 정렬 쌍의 수를 반환합니다.
}

// MergeSort 함수는 벡터를 정렬하고, 역순 정렬 쌍의 수를 반환합니다.
int MergeSort(vector<int>& v, int left, int right) 
{
  int cnt = 0; // 역순 정렬 쌍의 수를 저장하는 변수
 
  // 벡터에 두 개 이상의 요소가 있으면 분할하고 병합합니다.
  if (left < right) 
  {
    int mid = (right + left) / 2; // 중간 인덱스를 계산합니다.

    cnt = MergeSort(v, left, mid); 			// 왼쪽 부분 배열을 정렬하고, 역순 정렬 쌍의 수를 더합니다.
    cnt += MergeSort(v, mid + 1, right); 	// 오른쪽 부분 배열을 정렬하고, 역순 정렬 쌍의 수를 더합니다.
    cnt += Merge(v, left, mid + 1, right);  // 두 부분 배열을 병합하고, 역순 정렬 쌍의 수를 더합니다.
  }

  return cnt > 1000000000 ? -1 : cnt; // 역순 정렬 쌍의 수가 1000000000을 초과하면 -1을 반환하고, 그렇지 않으면 역순 정렬 쌍의 수를 반환합니다.
}

// solution 함수는 주어진 벡터를 정렬하고, 역순 정렬 쌍의 수를 반환합니다.
int solution(vector<int> &A) {
    
    return MergeSort(A, 0, A.size()-1); // 벡터를 정렬하고, 역순 정렬 쌍의 수를 반환합니다.
}

---