[python] bisect 사용법 / 이분탐색

Leetcode group-anagrams[link] 풀고 테스트 케이스에서 문제 발생

 

문제 발생

from typing import List
def group_anagrams(strs:List[str]) -> List[List[str]]:
    from collections import defaultdict
    resp = defaultdict(list)
    for s in strs:
        resp[''.join(sorted(s))].append(s)

    return sorted(list(resp.values()), key=len)


class TestGroupAnagrams:
    def test_one(self):
        strs = ["eat","tea","tan","ate","nat","bat"]
        assert group_anagrams(strs) ==  [['bat'],['nat','tan'],['ate','eat','tea']]

 

위 파일을 pytest로 테스트를 돌려본 결과 아래와 같은 결과값으로 인해 

AssertionError 발생 

[['bat'], ['tan', 'nat'], ['eat', 'tea', 'ate']]

---

해결책

리스트에 append 시 알파벳 순서로 안한 것 같아서 bisect를 활용합니다. 

def group_anagrams(strs:List[str]) -> List[List[str]]:
    from collections import defaultdict
    import bisect
    resp = defaultdict(list)
    for s in strs:
        bisect.insort(resp[''.join(sorted(s))], s)

    return sorted(list(resp.values()), key=len)

아마 bisect로 이분탐색시만 할 경우

time complexity가 O(log n)로 기억을 하고 있는데,

insort까지 하기 때문에 O(n)이 되지 않을까 생각합니다.

---

Bisect

bisect 라이브러리에는

bisect, insort 두가지가 있는데

bisect 는 단순하게 어디에 넣어야 하는지 위치만을 반환하며 

insort 는 실질적으로 insert를 해준다는 차이가 있습니다. 

 

_left, _right 으로 위치 변경도 할 수 있으니 공식 문서에서 확인해보시면 될 것 같습니다. [공식문서]

import bisect

x = [1,2,3,4,5,6,7]
bisect.bisect(x,3)
>>> 3   

bisect.insort(x,3) 
print(x)
>>> [1, 2, 3, 3, 4, 5, 6, 7]

 

 

마음이 편안해지는 테스트 케이스로 끝

day05.py::TestGroupAnagrams::test_one PASSED                                                                            [ 33%] 
day05.py::TestGroupAnagrams::test_two PASSED                                                                            [ 66%] 
day05.py::TestGroupAnagrams::test_three PASSED                                                                          [100%]