67번 문제 질문입니다(leetcode 349)

[heesungkim010]

안녕하세요. 67번 문제를 다음과 같이 딕셔너리를 이용해서 풀어봤는데요. 이렇게 하면 시간복잡도가 O(N)이라서 제일 나을거라고 생각했습니다.

그런데 실제로 실행 시간은 교재에 있는 O(NlogN) 풀이랑 거의 차이가 없더라고요. 그리고 가끔 다른 문제들 풀다가 보면 이렇게 딕셔너리를 이용해서 풀면 검색이 O(1)이라 실행이 빠를거라고 생각했는데 timeout 나는 경우가 있더라고요.

그래서 딕셔너리에서 검색이 O(1)이라는 것에 의존하는게 약간 위험할 수도 있다는 생각이 들었는데요. 제가 이해한 대로 딕셔너리가 O(1)이라는 것에 의존하는게 위험한 경우가 생길 수도 있나요? 그리고 만약 그렇다면, 언제 그게 위험할지를 예상할 수 있을까요?

` ' class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: count_dict_1 = { } count_dict_2 = { } result = []

    for num in nums1:
        count_dict_1[num] = 1

    for num in nums2:
        count_dict_2[num] = 1

    for key in count_dict_2.keys():
        if key in count_dict_1:
            result.append(key)

    return result

`

[likejazz]

파이썬의 딕셔너리는 실제로 O(1)으로 동작합니다. 다만 파이썬은 CPython이 실행하는 인터프리터이기 때문에 내부의 오퍼레이션에 따라 속도에 영향을 많이 받습니다. 실행속도를 줄이는게 목표라면 슬라이싱 등 파이썬에서 기본 제공하는 함수를 사용하는 편이 더 유리합니다. 리트코드도 사용자가 많아서인지 최근에는 아주 큰 테스트케이스는 제공하지 않고, 또한 애초에 O(n)과 O(nlogn)은 차이가 크지 않습니다.

[heesungkim010]

감사합니다