[2021][01]Created Sorted Array through Instructions

최광현·2021년 1월 16일
0

LeetCode

목록 보기
5/9

문제 정보

문제 설명

문제 요약

instructions 배열이 주어졌을 때, 빈 컨테이너 nums에 왼편에서 오른편으로 instuction을 하나씩 삽입했을 때 삽입비용의 최소합을 구하시오. 다만 최소비용이 매우 커질 수 있기때문에 10^9 + 7로 나눈 나머지를 반환하시오.

각 삽입의 최소비용은 다음 방법에 의한다

  • 현재 nums에서 instructions[i]보다 엄격하게 작은 수의 갯수를 구한다.
  • 현재 nums에서 instructions[i]보다 엄격하게 큰 수의 갯수를 구한다.

예를 드면, nums = [1,2,3,5]에 3을 삽입한다고 가정하면, 삽입비용은 min(2,1)이다. (1과 2는 3보다 작고, 5는 3보다 크다) 그래서 nums는 [1,2,3,3,5]가 될 것이다.

제약 조건

  • 1 <= instruction.length <= 10^5
  • 1 <= instructions[i] <= 10^5

문제 접근

instructions을 하나씩 집어넣을 때 마다, nums 배열에서의 엄격하게 자기보다 작은 수의 수와 nums 배열에서 엄격하게 자기보다 큰 수의 수를 알아야 한다는 점에서 이진탐색(binary search)로 풀면 되겠다는 생각이 들었다.

기본적인 binary search에서 조금 더 나아간 문제인데, 파이썬에서의 bisect 모듈을 이용하면 풀 수 있다. 파이썬의 bisect 모듈을 사용하지 않을 경우를 대비해서 swift에서는 bisect_left를 구현하여 풀어보았다.

bisect_left는 같은 크기의 수가 들어왔을 때 가장 왼쪽 위치를 반환하며, bisect는 같은 크기의 수가 들어왔을 때 가장 오른쪽 위치를 반환한다. bisect_leftbisect를 이용하여 현재 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
profile
Being a programmer

0개의 댓글