[문제3번] 두수의 합 : O(nlogn)
136
10 asked
제가 작성한 코드도 O(nlogn)에 충족하는지 궁금합니다 감사합니다
def solution(nums, target):
answer = [0]*2
length = len(nums)
nums = sorted(nums)
left = 0
right = length-1
for i in range(length):
if target > (nums[left] + nums[right]):
left += 1
if target < (nums[left] + nums[right]):
right -= 1
if target == (nums[left] + nums[right]):
answer = [nums[left], nums[right]]
return answerAnswer 1
0
안녕하세요, 인프런 AI 인턴입니다. parksangil99님.
두 수의 합 문제에서 O(nlogn)의 시간 복잡도를 가지고 있는지 확인하고 싶으시군요.
우선, 정렬을 사용하는 부분에서 시간 복잡도는 O(nlogn)입니다. 그 다음, 투 포인터 접근 방식으로 두 수의 합을 찾는 부분은 O(n) 시간 복잡도를 가집니다. 따라서 전체 코드의 시간 복잡도는 O(nlogn) + O(n)으로, 최종적으로 O(nlogn)에 해당합니다.
하지만, 코드에서 약간의 수정이 필요합니다. 현재 for 루프 내에서 모든 경우를 확인하지 않고, 필요한 경우에만 인덱스를 조정하는 방식으로 충분합니다. 다만, target을 찾았을 때 루프를 종료하도록 수정할 필요가 있어 보입니다.
다음은 최적화된 코드입니다:
def solution(nums, target):
answer = [0]*2
nums = sorted(nums)
left = 0
right = len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
answer = [nums[left], nums[right]]
break
elif current_sum < target:
left += 1
else:
right -= 1
return answer
관련하여 유사한 질문 및 답변들은 다음 링크들을 참고해주세요:
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.
백준 서비스 종료인데 도전 과제 프로그래머스 문제로 올려주실수 있으신가요
0
59
1
도전과제 질문있습니다
0
69
2
안녕하세요 강사님 파이썬 커리큘럼 문의드립니다..
0
86
2
두수의합 sorting 질문
0
141
1
두수의합 Counter 사용
0
161
2
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
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
310
1