https://codility.com/demo/results/demoBD476U-K6K/
Task description
A zero-indexed array A consisting of N integers is given. An inversionis a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].
Write a function:
class Solution { public int solution(int[] A); }
that computes the number of inversions in A, or returns −1 if it exceeds 1,000,000,000.
Assume that:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
For example, in the following array:
A[0] = -1 A[1] = 6 A[2] = 3 A[3] = 4 A[4] = 7 A[5] = 4
there are four inversions:
(1,2) (1,3) (1,5) (4,5)
so the function should return 4.
Complexity:
- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
------------------ 풀이 --------------------------
Code: 09:34:39 UTC, java, final, score: 100.00
Analysis
Detected time complexity:
O(N*log(N))
O(N*log(N))
| test | time | result | |
|---|---|---|---|
| Example tests | |||
| example1 example test | 1.464 s | OK | |
| Correctness tests | |||
| simple1 | 1.472 s | OK | |
| simple2 | 1.476 s | OK | |
| simple3 | 1.452 s | OK | |
| extreme_0_inv [0], [], [1,2,3], [1,1,1] | 1.528 s | OK | |
| medium1 n=100 | 1.468 s | OK | |
| medium2 n=200 | 1.472 s | OK | |
| Performance tests | |||
| medium3 n=1000 | 1.464 s | OK | |
| big1 n=10000 | 1.512 s | OK | |
| big2 n=20000 | 1.588 s | OK | |
| big3 n=30000 | 1.620 s | OK | |
---------- test code ------------------------------
public class Distinct{
int [] global_A;
public int solution(int[] A){
global_A = A.clone();
return mergesort(global_A,0,global_A.length-1);
}
public int mergesort(int[]A, int first, int last){
int mid = (first+last)/2;
int left_inver, right_inver;
if(first < last){
//Recursive calling
left_inver = mergesort(A, first, mid);
if(left_inver == -1)
return -1;
right_inver = mergesort(A, mid+1, last);
if(right_inver == -1)
return -1;
}
else{ // Terminate condition
return 0;
}
int first_index = first; // 왼쪽 부분값의 인덱스
int second_index = mid+1; // 오른쪽 부분의 인덱스
int[] temp = new int[last-first+1];
int temp_index = 0;
int merge_inver = 0; // inversion한 횟수
//왼쪽 인덱스의 위치가 mid보다 작고 오른쪽 인덱스 위치가 last보다 작을때까지 반복
while(first_index <= mid && second_index <= last){
// P < Q 에 해당하지 않기 때문에 inversion이 이루어 지지 않는 조합
if(A[first_index] <= A[second_index]){
temp[temp_index] = A[first_index];
first_index++;
}
else{
//인덱스 최대값이 작은 값에 해당하므로, inversion이 존재하는 경우
/* 예를들어
* [ 4, 5, 2, 3]
* [left part | right part]
* first_index가 현재 1이고, second_index가 3이고, mid가 2이면
* 여기서 필요한것은 2입니다. 그렇기 때문에 4,5를 inversion하지 않고 2로 접근해야합니다.
*
* 이후, 왼쪽 부분이 정렬이되고 , 모든 값들은 first_index 시작부터 끝까지 second_index보다 크게 됩니다.
* 그리고 그것보다 작은 indexes를 가지는 거죠
* 결과적으로 mid - first_index +1 이 출력되는 것입니다.
*/
temp[temp_index] = A[second_index];
second_index ++;
merge_inver += mid - first_index +1;
if(merge_inver > 1000000000)
return -1;
}
temp_index ++;
}
// while의 조건을 통해 inversion이 발생할 필요없는 부분을 지나치고
// 이후 inversion이 발생
// 왼쪽 부분의 값들은 왼쪽에 있는데 그것들은 작은 indexes값을 가지고 있습니다.
// 하지만 값은 크죠, 즉, inversion이 이루어 져야할 부분입니다.
// 주의해야할 것은 이러한 inversion횟수는 이미 계산되었습니다.
if(first_index != mid+1){
while(first_index <= mid){
temp[temp_index] = A[first_index];
first_index ++;
temp_index ++;
}
}
// 오른쪽 부분의 값들은 오른쪽에 있고, 이것들은 왼쪽의 값과 인덱스보다 높은 indexes와 값을 가지고 있습니다.
// 즉, inversion이 이루어지면 안되는 부분입니다.
if(second_index != last+1){
while(second_index <= last){
temp[temp_index] = A[second_index];
second_index ++;
temp_index ++;
}
}
// temp 배열에 넣었던 값들을 다시 A배열로 옮깁니다.
int copy_index = first;
for(int i=0; i <temp_index; i++){
A[copy_index] = temp[i];
copy_index++;
}
if(merge_inver + left_inver + right_inver > 1000000000)
return -1;
else
return merge_inver + left_inver + right_inver;
}
public static void main(String args[]){
Distinct d = new Distinct();
int [] A ={-1, 6, 3, 4, 7, 4};
System.out.println(d.solution(A));
}
}