3-8 출석체크 문제 질문

작성한 질문수 1

0

딸바맛있따님 좋은 질문 감사합니다!!

1. 시간 복잡도는 똑같습니다

둘 다 O(N)이에요. 딕셔너리든 set이든 둘 다 해시 테이블 기반이거든요.

강의 방법: O(N + M) → O(N) 제안 방법: O(M + N) → O(N)

Big-O 표기법으로는 차이가 없어요.

2. 실제 연산 횟수에서 차이가 나요

강의 방법: 삽입 9번 + 삭제 8번 = 17번 해시 연산

제안 방법: 삽입 8번 + 조회 평균 4.5번 = 12.5번 해시 연산

제안 방법이 평균적으로 30% 정도 연산이 적어요. 그리고 삭제 연산이 되게 무거운 편이라서 제안해주신 방법이 훨씬 이득입니다!

3. 공간 복잡도 차이

강의 방법: O(N) - all_array 전체 저장 (9명)

제안 방법: O(M) - present_array만 저장 (8명)

present_array가 항상 더 작으니까 메모리를 조금 덜 써요.

4. 조기 종료 가능 여부

강의 방법: 무조건 all_array, present_array 전부 순회

제안 방법: all_array 순회 중 결석자 찾으면 바로 return

최선의 경우 1명만 확인하고 끝날 수 있어요.

5. 실전에서는요?

이 문제처럼 N이 작으면 (수십 명) 체감되는 차이는 거의 없어요. 둘 다 밀리초 안에 끝나거든요.

하지만 N이 10만, 100만 되면 제안 방법이 확실히 유리해요. 특히 결석자가 앞쪽에 있으면 조기 종료로 엄청 빨라지고요.

6. 최종 답변

성능상 "약간" 더 빠릅니다. 중요한 건 둘 다 해시를 쓴다는 거예요. 이중 반복문 O(N²)을 해시로 O(N)으로 줄인 게 핵심이고, 딕셔너리냐 set이냐는 디테일의 차이지만, 이렇게 여러가지 생각해보시면서 개선하려는 모습 넘넘 좋습니다!! 언제든 더 시도해보시면서 개선시켜보시길 추천드립니다!!1

0

안녕하세요, 인프런 AI 인턴입니다. 딸바맛있다님.

질문해주신 출석체크 문제에서 present_array를 먼저 set에 담아두고 all_array를 순회하면서 확인하는 방법은 시간 복잡도와 성능 측면에서 매우 효율적인 전략입니다.

설명:

• set 자료구조: Python의 set은 내부적으로 해시 테이블을 사용하여 평균적으로 O(1)의 시간 복잡도로 원소 존재 여부를 확인 가능합니다.
  
• 코드 설명:
  

  
  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
  

  
  위 코드에서 present_array를 set으로 변환하면, 각 학생이 출석했는지를 확인할 때 평균 O(1)로 빠르게 확인할 수 있습니다. all_array를 순회하면서 set을 이용해 출석 여부를 체크하는 것은 성능 측면에서 매우 효율적이며, 전체적인 시간 복잡도는 O(N)입니다. 여기서 N은 all_array의 길이입니다.
  

결론:

이 방식은 단순히 반복문 내에서 리스트로 확인하는 것보다 훨씬 빠르며, 특히 all_array가 크다면 성능의 차이가 두드러질 수 있습니다.

관련된 유사한 질문을 확인하고 싶으시다면, 아래의 링크를 참고하시기 바랍니다:

• 해시 충돌에서 링크드 리스트말고 해시테이블을 이용해서 구현하지 않는 이유가 있을까요?
  
• hash table 시간복잡도에 관한 질문
  

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.