inflearn logo
강의

Course

Instructor

Coding Test Core for Beginners (Theory and Problem Solving) [Python]

[Problem 1] Minimum Jump Code Implementation

체크배열을 set 으로 사용해도될까요?

248

PrivilegeEscalate

27 asked

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) 이어서 괜찮지않나 생각하는데 조언좀 부탁드리겠습니다!!

python 코딩-테스트

Answer 1

0

communityai8509

안녕하세요, 인프런 AI 인턴입니다.
PrivilegeEscalate님, 문제 풀이에 대한 질문 감사합니다.

네, set 자료구조를 사용해도 좋습니다. Python에서의 set은 해시 테이블을 기반으로 구현되어 있어서 평균적으로 O(1) 시간 복잡도를 갖는 addnot in 연산을 제공합니다. 따라서 중복 체크를 위한 용도로 적합합니다.

일반적인 배열을 사용하는 경우, 특정 요소가 배열 안에 존재하는지 확인하는데 O(n)의 시간이 소요될 수 있습니다. 따라서 큰 데이터셋을 다루는 경우나 중복 체크를 자주 해야 한다면 set을 사용하는 편이 효율적입니다.

주어진 코드에서 duplicateset으로 관리하는 것은 중복 체크를 더 효율적으로 수행할 수 있게 해주므로 좋은 접근 방법입니다.

백준 서비스 종료인데 도전 과제 프로그래머스 문제로 올려주실수 있으신가요

0

59

1

도전과제 질문있습니다

0

69

2

안녕하세요 강사님 파이썬 커리큘럼 문의드립니다..

0

86

2

두수의합 sorting 질문

0

141

1

두수의합 Counter 사용

0

161

2

[문제3번] 두수의 합 : O(nlogn)

0

136

1

set을 활용한 중복제거

0

198

2

[문제 5번] 중복제거

0

150

1

최소값의 위치

0

139

1

백준 사용 시 채점 언어

0

174

1

백준 10546 배부른 마라토너

0

154

1

고정된 숫자 문제 질문

0

209

2

답은 맞는거같은데 틀렸어요

0

202

1

강의 커리큘럼 질문있습니다.

0

239

1

배열리스트 문제 5번 <중복 제거> 질문입니다.

0

275

1

연결리스트의 삽입과 삭제에서 시간복잡도.

0

352

1

내장 함수들의 시간복잡도는 외워둬야하나요?

0

236

1

중복 제거

0

340

1

카드 점수 정확성 테스트 경우의 수 문의

0

187

1

완강 후 후속 강의, 공부법 질문..

0

372

2

cnt = 1 과 nums.sort() 의 순서가 바뀌어야하지 않나요?

0

274

2

nums 조건오류인가요?

2

303

1

최솟값의 위치

0

244

2

강의 3-6 두수의 합(해시) 질문

0

311

1