글 읽기 - 11003 시간 초과 질문

quf9484 3년 전 0

N이 5,000,000이라서 O(NlogN)으로 풀면 된다고 생각했습니다.

다른 질문에서 seg tree 사용하셔서 에러 난 질문이 있는데 저도 비슷한 이유인가요??

고수님들 도와주시면 정말 감사합니다 ㅜㅜ

import sys
from bisect import bisect_left
input = sys.stdin.readline

N, L = map(int, input().split())
arr = list(map(int, input().split()))
window = []

for i in range(len(arr)):
    if i >= L:
        del window[bisect_left(window, arr[i-L])] # L 만큼 이전에 들어온 수 제거

    num = arr[i]
    index = bisect_left(window, num) # 새로운 값이 들어 갈 위치
    window.insert(index, num)    
    print(window[0], end=' ')

quf9484 3년 전 0

답변 감사드립니다.

추가 질문이 있습니다!

1. NlogN으로 풀면 안 되는 문제인가요?

2. 문제를 보고 어떻게 O(n)이 정해인 것을 파악할 수 있을까요?

1.
시간제한상 어떻게 잘 최적화하면 될거 같다는 생각입니다. 저는 안해봤습니다만 맞은 분들 풀이중에 세그풀이가 있긴 있네요.(아슬아슬 합니다)
2.
이건 판단을 못하는게 맞는거 같습니다.
만약 제 입장에서 이 문제를 대회에서 만났다면, O(NlogN)풀이가 먼저 떠올렸다면 일단 넣어 볼거 같습니다.
실제로 데이터가 약하거나, 잘 최적화 한다면 계산상 시간복잡도가 애매하더라도 뚫리는 경우가 많으니까요.
하지만, 이 문제는 질문게시판 현황을 보시면 아시겠지만, 시간제한이 중간에 수정되었습니다.
의도적으로 세그트리 풀이를 막아 놓고, 정해를 의도한 것이라고 생각됩니다.

quf9484 3년 전 0

답변 정말 감사합니다!

도움 많이 됐습니다.

djs100201 3년 전 1

입력이 너무 커서 추가로 굉장히 많은 시간이 드나 보네요.
어떻게 입출력을 잘 최적화 하면 되나 보네요 ㅠ
https://panty.run/fastio/
링크하나 혹시 몰라 남깁니다..

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

문제

문제

출처

ICPC

11003 시간 초과 질문

quf9484 3년 전 0

djs100201 3년 전 0

quf9484 3년 전 0

djs100201 3년 전 1

quf9484 3년 전 0

djs100201 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말