인프런 커뮤니티 질문&답변
작성한 질문수
체크배열을 set 으로 사용해도될까요?
작성
·
161
·
수정됨
0
from collections import deque
def solution(home):
answer = 0
duplicate = {0}
queue = deque([0])
while queue:
node_length = len(queue)
for _ in range(node_length):
node = queue.popleft()
if node == home:
return answer
for child_node in [node - 1, node + 1, node + 5]:
if (0 < child_node < 10_000) and (child_node not in duplicate):
duplicate.add(child_node)
queue.append(child_node)
answer += 1
강의가 드디어 거의 끝나가네요.. 해당문제를 혼자 풀어봤습니다. 강의에서는 체크배열로 중복을 체크하더군요! 이 중복체크를 체크배열이 아닌 set 로 해결해도 효율적일까요? 어짜피 set 의 시간복잡도는 O(1) 이어서 괜찮지않나 생각하는데 조언좀 부탁드리겠습니다!!
답변 1
0
안녕하세요, 인프런 AI 인턴입니다.
PrivilegeEscalate님, 문제 풀이에 대한 질문 감사합니다.
네, set 자료구조를 사용해도 좋습니다. Python에서의 set은 해시 테이블을 기반으로 구현되어 있어서 평균적으로 O(1) 시간 복잡도를 갖는 add 및 not in 연산을 제공합니다. 따라서 중복 체크를 위한 용도로 적합합니다.
일반적인 배열을 사용하는 경우, 특정 요소가 배열 안에 존재하는지 확인하는데 O(n)의 시간이 소요될 수 있습니다. 따라서 큰 데이터셋을 다루는 경우나 중복 체크를 자주 해야 한다면 set을 사용하는 편이 효율적입니다.
주어진 코드에서 duplicate를 set으로 관리하는 것은 중복 체크를 더 효율적으로 수행할 수 있게 해주므로 좋은 접근 방법입니다.