100년 전쟁 관련 질문 amievil2 안녕하세요. 1번에 올라와 있는 백년 전쟁 문제를 보고 쉬울 것 같아서 도전했는데 역시 성공률이 낮은 이유가 있었군요. T.T Q 처리시간이 O(N) 이고 T 처리시간 O(1) 인데도 시간 초과가 나오네요. 문제 푸신분 계시면 혹시 답해 주세요. Q와 T에 대한 처리시간을 O(logN)으로 푸셨나요? 아니면 Q는 O(1) T가 O(N) 이면 괜찮을려나? 힌트 및 도움 부탁드립니다. 10년 전
1개의 댓글이 있습니다. VOCList 쿼리의 개수가 5만개인데, Q에 대한 처리시간이 N이라면 전체 진행시간은 얼추 5만의 제곱에 비례하게 됩니다. 제한시간 내에 돌아가기엔 좀 크지요.. T가 N에 비례하는 경우도 역시 5만의 제곱에 비례하게 되어 시간초과가 날 것 같습니다. 둘 다 lgN에 비례할 경우에는 (5만 * lg5만) 에 비례하게 되어 시간제한 이슈는 피할 수 있을 것 같네요 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
amievil2
안녕하세요.
1번에 올라와 있는 백년 전쟁 문제를 보고 쉬울 것 같아서 도전했는데 역시 성공률이 낮은 이유가 있었군요. T.T
Q 처리시간이 O(N) 이고 T 처리시간 O(1) 인데도 시간 초과가 나오네요.
문제 푸신분 계시면 혹시 답해 주세요.
Q와 T에 대한 처리시간을 O(logN)으로 푸셨나요?
아니면 Q는 O(1) T가 O(N) 이면 괜찮을려나?
힌트 및 도움 부탁드립니다.
10년 전