34707번 - 세미-연속 수열
제출 번호 : 101507201
제 코드의 시간복잡도는 O(n^2)이라 시간초과가 발생해야하는데 통과합니다.
테스트 케이스를 추가해주세요.
슬라이딩 윈도우를 한 칸씩 이동할 때마다 최대값이나 최소값이 바뀐다면 O(K)만큼 걸리고 O(N-K)만큼 발생하니, O(K *(N-K))이 걸립니다. 이 때 K가 2/N이라면 O(N^2/4) 만큼 걸려서 시간초과가 나야할 것 같습니다.
100000 50000 (1).txt
댓글을 작성하려면 로그인해야 합니다.
ps9319 10달 전 1
제출 번호 : 101507201
제 코드의 시간복잡도는 O(n^2)이라 시간초과가 발생해야하는데 통과합니다.
테스트 케이스를 추가해주세요.
슬라이딩 윈도우를 한 칸씩 이동할 때마다 최대값이나 최소값이 바뀐다면 O(K)만큼 걸리고 O(N-K)만큼 발생하니, O(K *(N-K))이 걸립니다. 이 때 K가 2/N이라면 O(N^2/4) 만큼 걸려서 시간초과가 나야할 것 같습니다.
100000 50000 (1).txt