0713 How many shifts when doing an insertion sort
해커랭크의 Insertion Sort Advanced Analysis
솔직히 드럽게 오래 걸림. 결국 Discussions보고 binary indexed tree(BIT)로 해결했다.
\(O( n \log n)\)과 \(O(n^2)\)는 정말 무시무시한 차이였음. n이 100k에 이르면 \(O(n^2)\)는 끝나지도 않는다.
아래는 내 것인데, 구간합을 구하는 빠른 방법이 BIT를 이용하는 것이어서 그대로 한 것이지만, 뒤에 <Problem setter's code>를 보면, 이 답은 정말 바보같다는 것을 알 수 있다.
# Enter your code here. Read input from STDIN. Print output to STDOUT
#!/usr/bin/python
def getsum(idx, itvsum):
sumv = 0
while idx>0:
sumv += itvsum[idx]
idx -= (idx & -idx)
return sumv
n = input()
for iterate in range( n ):
x = input()
a = [ int( i ) for i in raw_input().strip().split() ]
b = sorted(set(a)) # what the...
num2idx = {}
for i, val in enumerate(b):
num2idx[val] = i+1
ln2i = len(num2idx)
interval_sum = [0]*(ln2i+1) # 1 base
ans = 0
total_cnt =0
for ai in a:
idx = num2idx[ai]
#get sum
ans += total_cnt - getsum(idx, interval_sum)
#insert new element to interval_sum
while idx <= ln2i:
interval_sum[idx] += 1
idx += (idx & -idx)
total_cnt += 1
print ans
Problem setter’s code
아래는 짧고 아름다운 모범답안.훌륭하다 훌륭해 정말 훌륭하다 두가지 성질을 이용한다.
하나는, shift의 개수를 셀 때, element를 하나씩 넣는 것이 아니고 아예 sorted array 둘을 합하는 과정으로 이해해도 구할 수 있다는 점을 이용. 즉, sorted array A, B가 있을 때, cost([A, B]) = cost(A) + cost(B) + \(\alpha\)이고 sorted array라는 가정이 있기 때문에 \(\alpha\)를 쉽게 계산할 수 있다.
def inversions(arr):
n = len(arr)
if n==1:
return 0
n1 = n/2
n2 = n - n1
arr1 = arr[:n1]
arr2 = arr[n1:]
ans = inversions(arr1) + inversions(arr2)
i1 = 0
i2 = 0
for i in range(n):
if i1 <n1 and (i2>=n2 or arr1[i1]<=arr2[i2]):
arr[i] = arr1[i1]
ans += i2
i1 += 1
elif i2 < n2:
arr[i] = arr2[i2]
i2 += 1
return ans
for _ in range(input()):
n = input()
arr = map(int,raw_input().split())
counts = inversions(arr)
print counts
다른 하나는, 15th line이 핵심. 각각의 element의 inversion을 계산하고 넘어가는 것이 아니라, 통째로 몇개의 inversion이 하나씩 증가하고 있다고 생각하고 연산. \(O(n)\)에 \(\alpha\)계산이 가능해진다. 웹에 같은 문제를 푼 사람이 있는데 필요하면 그 사람의 설명도 참조.
etc
두 코드의 속도를 비교해보면 내 코드가 상당히 빠르게 동작한다. 답안의 재귀호출이 시간을 상당히 많이 잡아먹는 모양. 대략 답안코드 수행시간의 70% 미만으로 걸린다. 아무리 빨라도 구린 것은 구린 것이다. 아니면 100배 빠르던가 sorted(set(a))라는 어처구니 없는 행동을 해도 수행시간이 더 빠른것 보면 native method의 무시무시함을 알 수 있다.