HackerRank Interview Preparation Kit > Sorting

HackerRank의 Interview Preparation Kit > Sorting의 Medium 이상 문제

Sorting: Comparator - medium

문제요약

n개의 [이름, 점수]들을 점수순 내림차순 정렬, 점수가 같을 경우 이름 오름차순으로 정렬 후 출력하는 class 작성

Sample Input

5 amy 100 david 100 heraldo 50 aakansha 75 aleksa 150

Sample output

aleksa 150 amy 100 david 100 aakansha 75 heraldo 50

풀이

__repr__, cmp_to_key

Fraudulent Activity Notification - medium

문제요약

은행에서 고객의 사용 내역을 분석해서 부정행위 알림을 보낸다. n일 동안의 사용 내역 expenditures와 분석을위한 기간 d일이 주어졌을 때, 이전 d일 동안 사용내역의 중앙값(홀수면 가운데, 짝수면 가운데 두 수의 평균)의 2배 이상으로 사용했다면 해당일에 알림을 보낸다. 예를들어 d=3이고 expenditures = [10, 20, 30, 40, 50]이면 첫 3일은 정보 수집기간이고 4일 째에 이전 3일의 중앙값이 20의 2배 이상이므로 알림을 보낸다. 5일 째에는 이전 3일의 중앙값 30의 2배 보다 적게 사용했으므로 알림을 보내지 않는다. 따라서 총 한 번의 알림이 간다. n, d, expenditures가 주어지면 알림이 가는 횟수를 구해서 반환한다. (1<= n<=2*10^5, 1<=d<=n, 0<=expenditure[i]<=200)

Sample Input

9 5 2 3 4 2 3 6 8 4 5

Sample output

2

풀이

문제 풀이 자체는 어렵지 않으나 timeout에 주의해야한다. 매번 이전 d일을 정렬하고 중앙값을 구하면 timeout이 발생. 이전 d일 동안은 정렬이 되어 있으니 다음 d일에는 가장 빠른 날짜의 값을 제외하고 새로운 값을 정렬된 상태에서 추가시키면 binary search를 통해 빠르게 정렬을 유지할 수 있다.

Merge Sort: Counting Inversions - Hard

문제요약

배열 arr에서 i < j일 때, arr[i] > arr[j]인 형태가 존재한다. 순서를 바로잡기 위해 인접한 요소들만 swap할 수 있다. d개의 datasets이 주어졌을 때 각각을 정렬하기 위해 수행해야 하는 swap의 수를 출력한다. (1<=d<=15, 1<=n<=10^5, 1<=arr[i]<=10^7)

Sample Input

2

5

1 1 1 2 2

5

2 1 3 1 2

Sample output

0

4

풀이

문제의 제목처럼 merge sort를 활용한다. 각 요소들이 순서에 맞는 제자리로 돌아가기 위해 swap을 하는 경우가 merge sort의 merge과정에서 오른쪽 part의 값을 왼쪽 part 사이에 추가되는 경우로 볼 수 있다.

즉, 1,2,4 / 1, 3, 5을 merge하면 처음엔 왼쪽 1, 그리고 오른쪽 1을 왼쪽 1다음으로 merge가 되는데 이 때 움직이는 거리를 계산하면 남은 왼쪽 part의 길이인 2가 된다. merge sort에서는 별도 메모리를 사용하지만 단순히 제자리에서 생각해보면 [1, 1], 2, 4 / 3, 5가 되므로 swap으로 간주하면 2번의 swap이 필요한셈이다. 따라서 merge sort 수행시 merge 과정에서 오른쪽 부분을 왼쪽 사이로 합치는 과정의 swap 수를 모두 계산하면 된다.

그러나 마찬가지로 timeout의 변수가 도사리고 있다. python으로 해본 결과 마지막 3개의 t.c에서 timeout이 발생하는데 pypy로 제출하면 정상 통과한다. python3로 해보려 했으나,,, 쉽지 않다.