글 읽기 - 여기서 시간을 줄이려면 뭘더해야하는 건가요 ??

dlcksdnd321 5년 전 0

문제에서 뭘더 요구하는지 잘모르겠습니다,..

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k=sc.nextInt();
		long[] h = new long[k];
		ArrayList<Long> ans = new ArrayList<Long>();
		int index=0;
		
		for (int i = k; i >0 ; i--) {
			long value = sc.nextLong();
			if (value==0) {
				if(index==0)
					ans.add((long) 0);
				else {
					heapsort(h);
					ans.add(h[h.length-1]);
					h[h.length-1]=0;
					index--;
				}
			}
			else {
				h[index]=value;
				index++;
			}
		}
		
		for (int i = 0; i < ans.size(); i++) {
			System.out.println(ans.get(i));
		}
	}
	
	 static void bulidMaxHeap(long[] h, int n) {
		for (int i = n ; i >=0; i--) {
			heapify(h,i,n+1);
		}
	}
	 
	static void heapify(long[] h , int index, int n) {// i 이전 노드는 힙하게하되 n이상 노드는 건들지말것!

		int leftChild = index*2+1;
		int rightChild =leftChild +1 ;
		int large1=0;
		if(leftChild>=n&&rightChild>=n) return;
		
		if(h[leftChild]>h[index]) 
			large1=leftChild;
		else
			large1=index;
		
		if(rightChild<n && h[rightChild]>h[large1])
			large1=rightChild;
		
		if(large1!=index) {
			swap(h,large1,index);
			heapify(h,large1,n);
		}
		if(large1==index)return;

			
	}
	
	static void heapsort(long[] h) {
		bulidMaxHeap(h, h.length-1);//먼저 기본 배열 힙하게 만들기  부모노드가 자식노드보다 크게
		for (int i = h.length-1; i >=1 ; i--) { 
			swap(h,0,i); // 0번째 배열 즉 최상위 노드와 i라는 최하의 오른쪽 노드에서 점점 왼쪽으로가는 변수와 자리바꾸기
			bulidMaxHeap(h,i-1); // i 번째는  정렬됬다 치고 i 빼고 0~i-1 최상위 노드 가장크게 힙하게
		}
	}
	static void swap(long[] h ,int i, int j) {
		long save=0;
		save=h[i];
		h[i]=h[j];
		h[j]=save;
	}
}

djm03178 5년 전 1

heapsort는 이 문제에 전혀 필요 없습니다. heapsort는 말 그대로 힙을 이용해서 정렬을 하는 것이고, 이 문제에서는 하나의 원소를 추가하는 연산과, 하나의 원소를 제거하는 연산만 지원하면 됩니다.

dlcksdnd321 5년 전 0

djm03178 블루레문제에 이어서 이렇게 도움주시다니 감사합니다!!!!!!!

정말 제게는 보이지 않는 선생님이십니다!!

항상행복하세요~~~

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

문제

문제

출처

ICPC

여기서 시간을 줄이려면 뭘더해야하는 건가요 ??

dlcksdnd321 5년 전 0

djm03178 5년 전 1

dlcksdnd321 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말