3-8 해쉬 -2

Question

def get_absent_student(all_array, present_array): all_set = set(all_array) present_set = set(present_array) return all_set - present_set 이런식으로 작성하였는데 해쉬 테이블을 사용한 방법과 비교했을 때 어떤 가요?

딩코딩코 · Answer

안녕하세요 ztmyLuv 님! 좋은 질문 감사합니다 Luv 님이 작성한 set 차집합 풀이, 매우 좋습니다! 실전 코딩테스트에서는 제안해주신 방식이 더 선호됩니다. 먼저 시간복잡도를 보면, 강의의 코드랑 둘 다 O(N)으로 동일합니다. Python의 set도 내부적으로 해시 테이블을 사용하기 때문이에요. set 생성에 O(N), 차집합 연산에 O(N)이 걸리고, 딕셔너리 방식도 순회와 삭제가 각각 O(N)이라 총 시간복잡도는 같습니다. 공간복잡도 측면에서는 set 방식이 두 개의 set을 만들어서 약간 더 메모리를 쓰긴 하지만, 실질적으로 O(N)이라 큰 차이가 없어요. 강의에서 딕셔너리를 사용한 이유는 해시 테이블이라는 자료구조의 동작 원리를 이해시키코자 했습니다 . 키를 넣고, 삭제하고, 남은 키를 찾는 과정을 명시적으로 보여주면서 해시 테이블이 어떻게 쓰이는지 체감할 수 있도록 했습니다. 실무나 실전에서는 Luv님처럼 set 연산을 활용하는 게 더 깔끔하고 좋은 코드입니다! 좋은 질문 감사합니다

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. ztmyLuv님. 질문해주신 코드는 set 자료구조를 활용하여 주어진 문제를 효과적으로 해결할 수 있는 좋은 접근입니다. 두 배열을 set 으로 변환한 후 차집합 연산( all_set - present_set )을 통해 간단하게 해결하고 있습니다. 해시 테이블과 비교: set 은 Python에서 이미 효율적인 해시 테이블 기반의 자료구조로, 평균적으로 O(1)의 시간 복잡도를 가집니다. 변환 및 연산 측면에서는 해시 테이블을 직접 구현한 것과 성능 면에서 대체로 유사 합니다. 시간 복잡도: all_array 와 present_array 를 set 으로 변환하는 데 각각 O(N)과 O(M)의 시간이 필요합니다. 차집합 연산 all_set - present_set 는 두 set 의 원소 수 중 작은 쪽에 비례하므로 O(M)입니다. 따라서 전체 시간 복잡도는 O(N + M)으로 효율적입니다. 이 방법은 코드가 간결하고 명확하여 Python에서 자주 사용하는 패턴 중 하나입니다. 성능이나 메모리 사용 면에서 본래 해시 테이블 사용 방식과 큰 차이가 없습니다. 관련 참고 링크: 비슷한 주제에 대한 추가 정보가 필요하시면 아래 링크를 참고하시면 좋습니다. - 해시 충돌에서 링크드 리스트말고 해시테이블을 이용해서 구현하지 않는 이유가 있을까요? - hash table 시간복잡도에 관한 질문 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.