인프런 커뮤니티 질문&답변

이희종님의 프로필 이미지

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

8. 침몰하는 타이타닉(그리디)

침몰하는 타이타닉 시간 복잡도/반례

23.05.12 19:51 작성

·

208

1

import sys
sys.stdin = open("input.txt", "rt")

n, m = map(int, input().split()) # n = 승객 수, m = 무게 제한
weight = list(map(int, input().split()))
weight.sort()

ans = 0
lt, rt = 0, n-1

while lt <= rt:
   if weight[lt] + weight[rt] <= m:
      ans += 1
      lt += 1
      rt -= 1
   else:
      ans += 1
      rt -= 1
      
print(ans)

문제의 답안으로 작성한 코드인데 해당 코드의 반례가 있는지 궁금하고, 강의에 나온 정답 코드와 비교했을 때 시간복잡도면에서 불리한지 궁금합니다!

답변 1

1

김태원님의 프로필 이미지
김태원
지식공유자

2023. 05. 13. 07:41

안녕하세요^^

잘 하신 코드입니다. 영상 뒷부분에 pop(0) 코드를 deque를 사용해 popleft로 개선을 하는데 위에 코드 lt, rt로 인덱싱하는게 popleft를 쓰는 것과 같은 시간복잡도입니다.