글 읽기 - java) 시간초과가 뜨는 이유를 모르겠습니다 ㅠ

jinia91 2년 전 0

히피파이가 log2n을 만족하게 짠거같고

힙 삭제 삽입도 제대로 구현한거같습니다.예제넣어돌려도 답도 나오는데

시간초과가 나오네요 ㅠㅠ

스트링빌더랑 버퍼리더를 씀에도 안되는데 뭐가 문제일까요

뭔가 무한루프에 빠지는 오류가 있는걸까요?

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

public class Main {

	static LinkedList<Integer> heapTree = new LinkedList<>();

	private static void heapify(LinkedList<Integer> a, int Pidx, int Lidx) {

		int lidx;
		int ridx;
		int largestidx;

		while (Pidx * 2 + 1 <= Lidx) {

			lidx = Pidx * 2 + 1;
			ridx = Pidx * 2 + 2;
			largestidx = Pidx;

			if (lidx <= Lidx && a.get(largestidx) < a.get(lidx))
				largestidx = lidx;
			if (ridx <= Lidx && a.get(largestidx) < a.get(ridx))
				largestidx = ridx;

			if (Pidx != largestidx) {
				swap(a, Pidx, largestidx);
				Pidx = largestidx;
			}
			
			else return;
			
		}
	}
	
	
	private static void swap(LinkedList<Integer> a, int Pidx, int largestidx) {
		int tmp = a.get(Pidx);
		a.set(Pidx, a.get(largestidx));
		a.set(largestidx, tmp);
		
	}
	
	
	
	private static int heapD(LinkedList<Integer> a) {
		swap(a, 0, a.size()-1);
		int x =a.pollLast();
		if (a.size() < 2)
			return x;
		
		heapify(a, 0, a.size()-1);
		return x;
	}
	
	
	private static void heapADD(LinkedList<Integer> a, int x) {
		a.offer(x);
		
		if (a.size() < 2)
			return;
		
		for(int i = a.size()-1; i>=0; i=(i-1)/2) {
			if(heapTree.get((i-1)/2)<heapTree.get(i)) {
				swap(a,(i-1)/2,i);
			}else break;
		}
	}
	
	

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.valueOf(br.readLine());

		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < N; i++) {
			int X = Integer.valueOf(br.readLine());

			if (X == 0) {
				if (heapTree.size() != 0) {
					sb.append(heapD(heapTree)).append("\n");
				} else
					sb.append("0").append("\n");

			}

			else {
				heapADD(heapTree, X);
			}
		}
		
		
		System.out.println(sb);
		
		
	}

}

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

문제

문제

출처

ICPC

java) 시간초과가 뜨는 이유를 모르겠습니다 ㅠ

jinia91 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말