글 읽기 - 시간복잡도 질문

justy 1년 전 0

제가 푼 코드로 하면 정렬을 제외하고 시간복잡도가 NlogN 이라고 알고 있습니다.
그런데, 이해가 되지 않는 점은
가방을 모두 돌음 => N
while 보석 => N
heapq (push / pop) => log N 이므로

시간복잡도는 (N^2)logN 이여야 하는 것이 아닌가요?
구글링을 해보니 while 부분은 시간복잡도에 포함을 시키지 않는 것 같던데 그 이유가 궁금합니다.

import sys
import heapq
n, k = map(int, sys.stdin.readline().split())
gems = []
for _ in range(n):
  heapq.heappush(gems, list(map(int, sys.stdin.readline().split())))
bags = []
for _ in range(k):
  bags.append(int(sys.stdin.readline().rstrip()))
bags.sort()

result = 0
values = []
for bag in bags:
  while gems and bag >= gems[0][0]:
    heapq.heappush(values, -heapq.heappop(gems)[1])
  if values:
    result -= heapq.heappop(values)
  elif not gems:
    break

print(result)

adung7 1년 전 0

14번줄 for문안에서 16번줄이 실행될때마다 gems를 계속해서 빼고 있어서 그렇습니다.

극단적으로 처음 15번줄 while문에 들어왔을때 gems원소를 다 빼면 어떻게 될까요 19번줄에 걸려 더이상 for문이 실행되지 않을것입니다.

따라서 for문안에서 15번줄의 while문은 최대 N(gems 갯수)번 추가로 실행될뿐입니다.

생략을 하지 않은 시간복잡도는 이와같을 것입니다. O(NlogN(정렬) + 2NogN)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간복잡도 질문

justy 1년 전 0

adung7 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말