3-8 해쉬 관련 다른 풀이도 궁금해요.

Question

1. 현재 학습 진도

몇 챕터/몇 강을 수강 중이신가요? 3-8 해쉬-2
어떤 알고리즘을 학습하고 계신가요? 해쉬
여기까지 이해하신 내용은 무엇인가요? 전체 이해 완료

안녕하세요 선생님 궁금한 점이 있어요.

HashTable의 경우에도 조회 성능이 최선일 경우 O(1)이고, set 자료구조에 포함되어 있는 지 여부조회도 O(1)로 이해를 했습니다!

해당 문제의 경우 set으로 변환하고 풀어도 시간복잡도 면에서 성능은 비슷하다고 봐도 될까요~?

def get_absent_student(all_array, present_array):
    present_students_set = set(present_array)
    for student in all_array:
        if student not in present_students_set:
            return student

딩코딩코 · Answer

안녕하세요 Tommy 님! 좋은 질문 감사합니다!!

맞습니다! HashTable과 Set 자료구조 모두 평균적인 조회 성능은 O(1)입니다. 따라서 제시하신 코드처럼 Set을 사용하여 문제를 해결하는 접근법은 시간복잡도 측면에서 매우 효율적입니다.

두 방식 모두 전체 시간복잡도는 O(n + m)으로 동일합니다. 여기서 n은 all_array의 길이, m은 present_array의 길이입니다.

set 방식의 장점은 코드가 더 간결하고 읽기 쉽습니다. 이번 문제에서는 학생의 유니크함을 보장하고 있기 때문에 더 명확하다고 할 수 있을 것 같습니다. 다만, 만약 동명이인이 나타난다면 어떻게 처리를 할지 정도 고려해봐도 좋을 것 같습니다

여러가지 고민을 해보시는 습관 너무 좋습니다! 완강까지 빠이팅입니다!

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. Tommy님.

질문하신 해시 테이블과 set을 사용한 접근 방식은 매우 유사한 시간복잡도를 가지며, 실제로 set은 내부적으로 해시 테이블을 기반으로 하여 이루어져 있기 때문에 O(1)의 평균적인 시간복잡도로 검색이 가능합니다.

코드 설명

present_students_set = set(present_array): 현재 출석한 학생들을 set 자료구조로 변환하여, 중복 없이 고유한 값의 집합을 만듭니다. set은 해시 테이블을 사용하여 검색과 삽입이 평균적으로 O(1)입니다.
for student in all_array: 모든 학생 목록을 순회하면서, 각 학생이 출석했는지를 확인합니다.
if student not in present_students_set: 각 학생이 출석한 집합에 있는지 확인하여, 출석하지 않은 학생을 찾습니다. 이 검사는 set을 사용하므로 평균 O(1)입니다.

따라서 전체 알고리즘의 시간복잡도는 all_array의 길이에 비례하여 O(N)입니다. 이는 매우 효율적이며, 해시 테이블을 직접 구현하는 것과 비교했을 때도 성능 면에서 크게 다르지 않습니다.

인프런 커뮤니티 질문&답변