글 읽기 - O(nlogn) 시간초과

tiro25 3년 전 0

우선순위큐를 이용하여 nlogn으로 풀었는데 시간초과가 나서 질문드려요.

n이 500만 까지지만 시간제한이 2초대여서 nlogn으로 해결할 수 있다고 생각했는데 선형으로만 시간이 되는건가요?

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Boj_최솟값찾기_11003 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken()), l = Integer.parseInt(st.nextToken());
		PriorityQueue<Pair> pq = new PriorityQueue<Pair>((o1, o2)->{
			if(o1.value == o2.value)
				return o1.index-o2.index;
			return o1.value-o2.value;
		});
		
		st = new StringTokenizer(br.readLine(), " ");		
		for(int i = 0; i < n; ++i) {
			int value = Integer.parseInt(st.nextToken());
			pq.offer(new Pair(value, i));
			Pair front = pq.peek();
			while(front.index < i-l+1) {
				pq.poll();
				front = pq.peek();
			}
			sb.append(front.value).append(' ');
		}
		System.out.println(sb);
	}

	static class Pair{
		int value;
		int index;
		public Pair(int value, int index) {
			this.value = value;
			this.index = index;
		}
	}
}

prarie 3년 전 2

시간 복잡도도 중요하지만 입력이 너무 커서 입출력 시간이 엄청 오래 걸립니다

Java11 소스들을 보니 BufferedReader, Writer 이용한 입출력 + O(N) 으로도 거의 2000ms ~ 인걸 보면 O(N log N) 으로는 힘들 것 같습니다

tiro25 3년 전 1

BufferedWriter를 써도 시간초과가 나서 cpp로 제출해보니 통과했어요 감사해요

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

문제

문제

출처

ICPC

O(nlogn) 시간초과

tiro25 3년 전 0

prarie 3년 전 2

tiro25 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말