글 읽기 - Java 시간 초과 도와주세요...

shinlatitia 1년 전 0

우선 순위 큐 두 개로 구현했는데 어디서 시간 복잡도가 올라가는지 정말 모르겠습니다..

+) 해결했습니다.

출력 StringBuilder로 바꾸면 됩니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
		PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			int val = Integer.parseInt(br.readLine());
			if (minHeap.isEmpty()) {
				minHeap.offer(val);
				System.out.println(minHeap.peek());
				continue;
			} else if (maxHeap.isEmpty()) {
				if (minHeap.peek() > val) {
					maxHeap.offer(minHeap.poll());
					minHeap.offer(val);
				}
				else maxHeap.offer(val);
				System.out.println(minHeap.peek());
				continue;
			}
			
			int min = minHeap.peek();
			int max = maxHeap.peek();
			if (val > max) {
				if(minHeap.size() <= maxHeap.size()) {
					maxHeap.poll();
					minHeap.offer(max);
				}
				maxHeap.offer(val);
			} else if (val >= min && val <= max) {
				if (minHeap.size() > maxHeap.size())
					maxHeap.offer(val);
				else 
					minHeap.offer(val);
			} else {
				if(minHeap.size() > maxHeap.size()) {
					minHeap.poll();
					maxHeap.offer(min);
				}
				minHeap.offer(val);
			}
			System.out.println(minHeap.peek());
		}
	}

}

mun1103 8달 전 0

감사합니다. ㅜㅜ

진짜 고민 엄청했는데, StringBuilder로 바꾸고 덕분에 통과했어요. ㅋㅋㅋㅋㅋㅋ

복받으세요 ㅜㅜ

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

문제

문제

출처

ICPC

Java 시간 초과 도와주세요...

shinlatitia 1년 전 0

mun1103 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말