중복 제거
340
14 asked
위의 코드도 O(n)의 시간복잡도를 가질까요?
Answer 1
0
안녕하세요, 인프런 AI 인턴입니다.
해당 코드의 시간 복잡도는 O(n)이 아닙니다. 리스트에서 pop() 연산은 O(1)의 시간 복잡도를 가지지만, if x not in answer 조건문은 리스트 answer를 처음부터 끝까지 확인하는 과정이 필요하며, 이는 최악의 경우 O(n)의 시간이 걸립니다. 따라서 중첩된 루프가 되며, 전체 시간 복잡도는 O(n^2)이 될 수 있습니다.
코드에서 반복문은 nums 리스트의 각 요소를 한 번씩 확인하되, 조건문은 answer 리스트에 해당 요소가 없는지 매번 확인합니다. answer 리스트의 길이가 길어질수록, in 연산에 더 많은 시간이 소요되므로, 전체적으로 각 요소를 확인하는 데에는 리스트의 길이만큼 시간이 걸립니다.
코드를 개선하여 O(n)의 시간복잡도를 가지게 하려면, 추가적인 자료 구조의 도움을 받아야 합니다. 예를 들어, 집합(Set)을 사용하여 이미 존재하는지 여부를 O(1)의 시간 복잡도로 확인할 수 있습니다.
백준 서비스 종료인데 도전 과제 프로그래머스 문제로 올려주실수 있으신가요
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
체크배열을 set 으로 사용해도될까요?
0
248
1
연결리스트의 삽입과 삭제에서 시간복잡도.
0
352
1
내장 함수들의 시간복잡도는 외워둬야하나요?
0
236
1
카드 점수 정확성 테스트 경우의 수 문의
0
187
1
완강 후 후속 강의, 공부법 질문..
0
372
2
cnt = 1 과 nums.sort() 의 순서가 바뀌어야하지 않나요?
0
274
2
nums 조건오류인가요?
2
303
1
최솟값의 위치
0
244
2
강의 3-6 두수의 합(해시) 질문
0
310
1