글 읽기 - (java)heap을 구현해서 풀었는데 시간초과가 나네요 ㅠㅠ 배열문제일까요?

poj4639 3년 전 2

minheap과 maxheap을 구현해서 중간값 이하는 maxheap으로 중간값이상은 minheap 으로 넣어서 maxheap의 peek값을 출력하도록 햇는데,

시간 초과가 나네요. heap을 구현하는 과정에서 arrayList를 사용해야 했을까요?

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

	public static void main(String[] args) throws IOException
	{
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] s =bf.readLine().split(" ");
		int n = Integer.parseInt(s[0]);
		maxheap max = new maxheap();
		minheap min = new minheap();
		for(int i=1;i<=n;i++)
		{
			s =bf.readLine().split(" ");
			int k = Integer.parseInt(s[0]);
			if(i%2==1)
			{
				max.push(k);
			}
			else
			{
				min.push(k);
			}
			if(i>=2)
			{
				if(max.heap[1]>min.heap[1])
				{
					int a=max.heap[1];
					int b=min.heap[1];
					max.pop();
					min.pop();
					max.push(b);
					min.push(a);
				}
			}
			bw.write(max.heap[1]+"\n");
			bw.flush();
		}
	}
	public static class maxheap
	{
		int[] heap = new int[100001];
		int heap_count =0;
		public maxheap() {}
		public void push(int num)
		{
			heap[++heap_count] = num;
			int cnt = heap_count;
			while(cnt>1&&heap[cnt/2]<heap[cnt])
			{
				int temp =heap[cnt];
				heap[cnt]=heap[cnt/2];
				heap[cnt/2]=temp;
				cnt = cnt/2;
			}
			return;
		}
		public int pop()
		{
			/*for(int i=1;i<=heap_count;i++)
			{
				System.out.print(heap[i]+" ");
			}*/
			//System.out.println(" 힙카운트" + (heap_count-1));
			int value=heap[1];
			heap[1]=heap[heap_count--];
			int cnt=1;
			while(cnt<=heap_count)
			{
				if(cnt>=heap_count)
				{
					break;
				}
				int next = cnt*2;
				if((next<heap_count)&&(heap[next]<heap[next+1]))
				{
					next++;
				}
				if(heap[cnt]>=heap[next])
				{
					break;
				}
				//System.out.println(heap[next]+" 교환 "+heap[cnt]);
				int temp = heap[next];
				heap[next]=heap[cnt];
				heap[cnt] = temp;
				cnt = cnt*2;
			}
			
			return value;
		}
	}

	public static class minheap
	{
		int[] heap = new int[100001];
		int heap_count =0;
		public minheap() {}
		public void push(int num)
		{
			heap[++heap_count] = num;
			int cnt = heap_count;
			while(cnt>1&&heap[cnt/2]>heap[cnt])
			{
				int temp =heap[cnt];
				heap[cnt]=heap[cnt/2];
				heap[cnt/2]=temp;
				cnt = cnt/2;
			}
			return;
		}
		public int pop()
		{
			/*for(int i=1;i<=heap_count;i++)
			{
				System.out.print(heap[i]+" ");
			}*/
			//System.out.println(" 힙카운트" + (heap_count-1));
			int value=heap[1];
			heap[1]=heap[heap_count--];
			int cnt=1;
			while(cnt<=heap_count)
			{
				if(cnt>=heap_count)
				{
					break;
				}
				int next = cnt*2;
				if((next<heap_count)&&(heap[next]>heap[next+1]))
				{
					next++;
				}
				if(heap[cnt]<=heap[next])
				{
					break;
				}
				//System.out.println(heap[next]+" 교환 "+heap[cnt]);
				int temp = heap[next];
				heap[next]=heap[cnt];
				heap[cnt] = temp;
				cnt = cnt*2;
			}
			
			return value;
		}
	}
}

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

문제

문제

출처

ICPC

(java)heap을 구현해서 풀었는데 시간초과가 나네요 ㅠㅠ 배열문제일까요?

poj4639 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말