글 읽기 - 질문입니다

lss5555 2년 전 0

이런식으로했는데 빠르게 정렬해줄수있는 방법을 찾기가힘드네요

단순 앞에거 뺴오는거면 되는데 몇번째꺼 이런식으로 뺴오니 빠른 시간복잡도로 구현하는 방법이 궁금합니다

import heapq
n,m=map(int,input().split())
la=list(map(int,input().split()))
lb=list(map(int,input().split()))
lc=list(map(int,input().split()))
ld=[]
for i in range(m):
      ld.append((lb[i],lc[i]))
ld.sort()
h=[]
for i in la:
      heapq.heappush(h,-i)
i=0
flag=1
while la:
    a,b=ld[i]
    i+=1
    if i==m:
          break
    if a<=-h[b-1]:
          h[b-1]+=a
    else:
          flag=0
          print(0)
          break
if flag:
      print(1)

rlawodud9394 2년 전 0

la를 counting sort로 정렬하시고

lc로 for문 돌리시면서 해당되는 la에서 해당되는 lb값을 빼고,

la에서 lb값을 빼도 정렬이 유지되야 하므로 뺀 la 값이 들어갈 index를 binary search로 찾아 넣어주시면

시간복잡도 O(NlogN) 되어 해결되네요

lss5555 2년 전 0

감사합니다 풀긴풀었는데 삽입과 정렬까지 nlogn이 나오긴하는데 for문이 최대 m (m==n이될수있음) 이렇게 되면

결국 시간복잡도가 n**2logn이되지않나요???다행히 그런 최악의 경우 케이스가없어서 뚤린것같은데 좀 신기하네여

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

문제

문제

출처

ICPC

질문입니다

lss5555 2년 전 0

rlawodud9394 2년 전 0

lss5555 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말