HackerRank MergeSort Counting Inversions
스왑의 횟수를 찾아내는 것이다.
Input
- 횟수
- 숫자 리스트 길이
- 실제 숫자 리스트 (공백으로 구분)
Bubble Sort 솔루션
속도 문제로 Timeout문제를 발생 시킴
def count_inversions(n,a,numSwap=0):
cumulatedNumSwap = 0
for i in range(0,n):
numSwap = 0
for j in range(0,n-1):
if a[j] > a[j+1]:
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
numSwap += 1
cumulatedNumSwap += numSwap
if numSwap == 0:
break
return cumulatedNumSwap
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
arr = list(map(int, input().strip().split(' ')))
numSwap = 0
numSwap = count_inversions(n,arr,numSwap)
print(numSwap)
출력결과
#input
2
5
1 1 1 2 2
5
2 1 3 1 2
#output
0
4MergeSort 솔루션
- MergeSort 자체는 문제가 아니다.
- Count를 할 때
count += mid - i + 1;이렇게 해야 한다는 점이 가장 어려운 부분이다. - 과도하게 문제가 꼬여 있다.
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static long countInversions(int[] arr){
return mergeSort(arr, 0, arr.length - 1);
}
public static long mergeSort(int[] arr, int start, int end){
if(start == end)
return 0;
int mid = (start + end) / 2;
long count = 0;
count += mergeSort(arr, start, mid); //left inversions
count += mergeSort(arr, mid + 1, end);//right inversions
count += merge(arr, start, end); // split inversions.
return count;
}
public static long merge(int[] arr, int start, int end){
int mid = (start + end) / 2;
int[] newArr = new int[end - start + 1];
int curr = 0;
int i = start;
int j = mid + 1;
long count = 0;
while(i <= mid && j <=end) {
if(arr[i] > arr[j]) {
newArr[curr++] = arr[j++];
count += mid - i + 1; // Tricky part.
}
else
newArr[curr++] = arr[i++];
}
// Leftover elements here.
while(i <= mid) {
newArr[curr++] = arr[i++];
}
while(j <= end) {
newArr[curr++] = arr[j++];
}
System.arraycopy(newArr, 0, arr, start, end - start + 1); // Usual stuff from merge sort algorithm with arrays.
return count;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int t = in.nextInt();
for(int a0 = 0; a0 < t; a0++){
int n = in.nextInt();
int arr[] = new int[n];
for(int arr_i=0; arr_i < n; arr_i++){
arr[arr_i] = in.nextInt();
}
System.out.println(countInversions(arr));
}
}
}'Computer Science > Coding Interview' 카테고리의 다른 글
| HackerRank Queues: A Tale of Two Stacks (0) | 2017.07.30 |
|---|---|
| Stacks: Balanced Brackets (0) | 2017.07.30 |
| HackerRank Data Structure (0) | 2017.07.30 |
| Binary Search (0) | 2017.07.28 |
| HackerRank: Basic Problems (0) | 2017.07.25 |
vimrc
