[Codility] Array Inversion Count
[Codility] Array Inversion Count
https://app.codility.com/programmers/trainings/4/array_inversion_count/start/
해결전략
정렬 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); // 벡터를 정렬하고, 역순 정렬 쌍의 수를 반환합니다.
}
'⭐ 코딩테스트 > Codility' 카테고리의 다른 글
[Codility] Disappearing Pairs (0) | 2024.02.19 |
---|---|
[Codility] Binary Gap (0) | 2024.02.18 |
[Codility] Tree Height (0) | 2024.02.18 |
[Codility] Tree Longest Zigzag (0) | 2024.02.18 |
[Codility] The Matrix (0) | 2024.02.17 |
댓글
이 글 공유하기
다른 글
-
[Codility] Disappearing Pairs
[Codility] Disappearing Pairs
2024.02.19 -
[Codility] Binary Gap
[Codility] Binary Gap
2024.02.18 -
[Codility] Tree Height
[Codility] Tree Height
2024.02.18 -
[Codility] Tree Longest Zigzag
[Codility] Tree Longest Zigzag
2024.02.18