인프런 커뮤니티 질문&답변
작성한 질문수
3-8 해쉬 -2
해결된 질문
작성
·
31
0
def get_absent_student(all_array, present_array):
all_set = set(all_array)
present_set = set(present_array)
return all_set - present_set이런식으로 작성하였는데 해쉬 테이블을 사용한 방법과 비교했을 때 어떤 가요?
답변 2
0
안녕하세요 ztmyLuv 님! 좋은 질문 감사합니다
Luv 님이 작성한 set 차집합 풀이, 매우 좋습니다! 실전 코딩테스트에서는 제안해주신 방식이 더 선호됩니다.
먼저 시간복잡도를 보면, 강의의 코드랑 둘 다 O(N)으로 동일합니다. Python의 set도 내부적으로 해시 테이블을 사용하기 때문이에요. set 생성에 O(N), 차집합 연산에 O(N)이 걸리고, 딕셔너리 방식도 순회와 삭제가 각각 O(N)이라 총 시간복잡도는 같습니다.
공간복잡도 측면에서는 set 방식이 두 개의 set을 만들어서 약간 더 메모리를 쓰긴 하지만, 실질적으로 O(N)이라 큰 차이가 없어요.
강의에서 딕셔너리를 사용한 이유는 해시 테이블이라는 자료구조의 동작 원리를 이해시키코자 했습니다 . 키를 넣고, 삭제하고, 남은 키를 찾는 과정을 명시적으로 보여주면서 해시 테이블이 어떻게 쓰이는지 체감할 수 있도록 했습니다. 실무나 실전에서는 Luv님처럼 set 연산을 활용하는 게 더 깔끔하고 좋은 코드입니다!
좋은 질문 감사합니다
0
안녕하세요, 인프런 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 시간복잡도에 관한 질문
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.