글 읽기 - 자바는 시간초과가 나는데, 서버 성능 문제인지...

junee0203 6년 전 0

뭐가 문젤까요...

모든걸 최소연산으로 처리했는데도, 시간초과라면, 누구의 문제죠... 자바의 문제인가요

import java.io.*;
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());
		Heap minHeap = new Heap(N+1);
		int input = 0;
		for(int i=0; i<N+1; i++) {
			input = Integer.parseInt(br.readLine());
			if(input==0)
				System.out.println(minHeap.delete());
			else
				minHeap.Insert(input);
		}
	}
	public static class Heap {
		private int[] arr;
		private int numOfData;
		public Heap(int N) {
			arr = new int[N];
			numOfData = 0;
		}
		public boolean isEmpty() {
			return numOfData == 0;
		}
		public void Insert(int data) {
			if(isEmpty()) {
				numOfData += 1;
				arr[numOfData] = data;
			}
			else {
				numOfData += 1;
				int current = numOfData;
				arr[current] = data;
				while(current != 1) {
					if(arr[current] >= arr[current/2]) {
						break;
					}
					else {
						arr[current] = arr[current/2];
						arr[current/2] = data;
						current = (current/2);
					}
				}
			}
		}
		public int getHighChild(int parent) {
			int left = parent*2;
			int right = parent*2+1;
			
			if(left > numOfData)
				return 0;
			else if(left == numOfData)
				return left;
			else {
				if(arr[left] < arr[right])
					return left;
				else
					return right;
			}
		}
		public int delete() {
			if(isEmpty())
				return 0;
			else {
				int willDeleted = arr[1];
				arr[1] = arr[numOfData];
				numOfData -= 1;
				int parentIdx = 1;
				int temp;
				int HighChildIdx;
				
				do {
					HighChildIdx = getHighChild(parentIdx);
					if(arr[parentIdx] <= arr[HighChildIdx]) {
						break;
					}
					else {
						temp = arr[parentIdx];
						arr[parentIdx] = arr[HighChildIdx];
						arr[HighChildIdx] = temp;
						parentIdx = HighChildIdx;
					}
				} while(parentIdx <= numOfData);
				return willDeleted;
			}
		}
	}
}

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

문제

문제

출처

ICPC

자바는 시간초과가 나는데, 서버 성능 문제인지...

junee0203 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말