bisect 정렬키 설정하기(부제: bisect 최고)

bisect 정렬키 설정

python 10 이전

• KeyWrapper 를 정의해서 쓰는 복잡한 방법이 존재한다.
  • 아직 디자인 패턴에 대한 이해가 얕다보니 명확하게 와닿는 건 아니지만
  • 래퍼(프록시)를 씌워서 키를 bisect에게 보여주고, 이를 이용해 정렬을 수행하되
  • 실제 아이템 요소를 보여줄 때는 키가 아닌 실제 데이터 값을 보여주도록 만든 것 같다.

from bisect import bisect_left, insort_left

class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

    def __len__(self):
        return len(self.it)

    ## 인서트 메소드는 커스터마이징 할 게 아니면 굳이 오버라이딩 할 필요는 없다
    def insert(self, index, item):
        print('asked to insert %s at index%d' % (item, index))
        self.it.insert(index, {"time":item})

timetable = [{"time": "0150"}, {"time": "0250"}, {"time": "0350"}, {"time": "0450"}, {"time": "0550"}, {"time": "0650"}, {"time": "0750"}]

bslindex = bisect_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")

islindex = insort_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")

from bisect import bisect_left

class KeyWrapper:
    def __init__(self, iterable, key):
        self.it = iterable
        self.key = key

    def __getitem__(self, i):
        return self.key(self.it[i])

    def __len__(self):
        return len(self.it)

data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
data.sort(key=lambda c: c[1])

newcol = ('brown', 7)

bslindex = bisect_left(KeyWrapper(data, key=lambda c: c[1]), newcol[1])
data.insert(bslindex, newcol)

print(data)

python 3.10 이후

# 딕트는 시퀀스가 아니어서 어쩔 수 없이 변환하고 정렬하는 것이 좋다
bslindex = bisect_left(KeyWrapper(timetable, key=lambda t: t["time"]), "0359")
timetable.insert(bslindex, {"time":"0359"})

import bisect
bisect.bisect_left(('brown', 7), data, key=lambda r: r[1])

How to use bisect.insort_left with a key?

• 안타깝게도 프로그래머스에서 이용하는 파이썬 버전은 3.8 이다. ㅠ

bisect.insort(list, value)

• python bisect.insort(list, value)

공홈 문서

• bisect - Array bisection algorithm - Python 3.10.7 documentation