instructions 배열이 주어졌을 때, 빈 컨테이너 nums에 왼편에서 오른편으로 instuction을 하나씩 삽입했을 때 삽입비용의 최소합을 구하시오. 다만 최소비용이 매우 커질 수 있기때문에 10^9 + 7로 나눈 나머지를 반환하시오.
각 삽입의 최소비용은 다음 방법에 의한다
예를 드면, nums = [1,2,3,5]에 3을 삽입한다고 가정하면, 삽입비용은 min(2,1)이다. (1과 2는 3보다 작고, 5는 3보다 크다) 그래서 nums는 [1,2,3,3,5]가 될 것이다.
instructions을 하나씩 집어넣을 때 마다, nums 배열에서의 엄격하게 자기보다 작은 수의 수와 nums 배열에서 엄격하게 자기보다 큰 수의 수를 알아야 한다는 점에서 이진탐색(binary search)로 풀면 되겠다는 생각이 들었다.
기본적인 binary search에서 조금 더 나아간 문제인데, 파이썬에서의 bisect 모듈을 이용하면 풀 수 있다. 파이썬의 bisect 모듈을 사용하지 않을 경우를 대비해서 swift에서는 bisect_left를 구현하여 풀어보았다.
bisect_left는 같은 크기의 수가 들어왔을 때 가장 왼쪽 위치를 반환하며, bisect는 같은 크기의 수가 들어왔을 때 가장 오른쪽 위치를 반환한다. bisect_left와 bisect를 이용하여 현재 nums에서 instructions[i]보다 작은 수의 갯수는 bisect_left을 얻은 값이고, instructions[i]보다 큰 수의 갯수는 현재 nums의 길이인 i에서 bisect를 통해 얻은 값을 빼면 얻을 수 있다.
class Solution:
def createSortedArray(self, instructions: List[int]) -> int:
answer = 0
arr = []
n = len(instructions)
MOD = 10 ** 9 + 7
for i, inst in enumerate(instructions):
l = bisect.bisect_left(arr, inst)
r = bisect.bisect(arr, inst)
answer += min(l, i - r)
arr[r:r] = [inst]
return answer % MOD