글 읽기 - 이문제 java로 풀었을때 질문입니다.

skqjacks 6년 전 0

C++로는 풀었는데 java로 풀어볼라고 했더니 시간초과가 계속 뜨는군요...... 이유를 모르겠습니다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Main{
	@SuppressWarnings("unused")
	public static void main(String args[]){
		Collection<Long> array1 = new ArrayList<Long>();
		Scanner scan = new Scanner(System.in);
		Long[] T;
		Long[] T1;
		
		int N = scan.nextInt();
		for(int i=0; i<N; i++){
			int x = scan.nextInt();
			int y = 0;
			Heap<Long> H = new MaxHeap<Long>(x);
			Heap<Long> H1 = new MinHeap<Long>(x);
			boolean ck[] = new boolean[1000001];
			for(int j=0; j<x; j++){
				String IO = scan.next();
				long data = scan.nextInt();
				if(IO.equals("I")){
					H.add(data);
					H1.add(data);
					ck[y] = true;
					y++;
				}
				else if(IO.equals("D")){
					while(H.size()>0 && !ck[H.index[0]]) H.remove();
					while(H1.size()>0 && !ck[H1.index[0]]) H1.remove();
					if(H.size() == 0) continue;
					if(data == 1){
						ck[H.index[0]] = false;
						H.remove();
					}
					else if(data == -1){
						ck[H1.index[0]] = false;
						H1.remove();
					}
				}
			} 
			//System.out.println(array);
			if(H.isEmpty()){
				System.out.println("EMPTY");
			}
			else {		
				System.out.print(H.remove() + " " + H1.remove());
			}
		}

	}
}

abstract class Heap<T extends Comparable<T>> implements HeapInterface<T> {

	public abstract int priority(T one, T two);
	/**
	 * This is the array containing your data. You MUST leave index 0 empty or
	 * your grade will be low. So start putting stuff at index 1, this will
	 * actually make the heap easier to implement.
	 */
	private T[] array;
	private int size;
	public int[] index = new int[1000001];
	/**
	 * Initializes the array with a default capacity of 11, and initializes the
	 * size to 0.
	 */
	public Heap() {
		// TODO Auto-generated method stub
		size = 0;
		array = (T[]) new Long[11];
	}

	/**
	 * Initializes the array with the given capacity, you do not need to do any
	 * checks on the capacity, it will be valid in our tests. and initialize the
	 * size to 0.
	 * 
	 * @param capacity
	 *            the starting capacity of the heap
	 */
	public Heap(int capacity) {
		// TODO Auto-generated method stub
		size = 0;
		array = (T[]) new Long[capacity];
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		if(size == 0) return true;
		return false;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public T getFirst() {
		// TODO Auto-generated method stub
		return null;
	}

	@Override
	public T remove() {
		// TODO Auto-generated method stub
		T res = null;
		if(isEmpty()){
			return (T) "Empty";
		}
		if(size > 0){
			res = array[0];
			size--;
			array[0]=array[size];
			index[0]=index[size];
			int at = 0;
			boolean done = size <= 0;
			while(!done){
				int left = at*2+1;
				int right = at*2+2;
				if(left < size ){
					if(right < size && array[at].compareTo(array[right]) < 0 && priority(array[at],array[right]) < 0){
						if(array[left].compareTo(array[right]) < 0){
							left = right;
						}
					}
					if(array[at].compareTo(array[left]) < 0 && priority(array[at],array[left]) < 0){
						T temp = array[at];
						int temp1 = index[at];
						array[at] = array[left];
						index[at] = index[left];
						array[left] = temp;
						index[left] = temp1;
						at = left;
					}
					if(right < size && array[at].compareTo(array[right]) > 0 && priority(array[at],array[right]) < 0){
						if(array[left].compareTo(array[right]) > 0){
							left = right;
						}
					}
					if(array[at].compareTo(array[left]) > 0 && priority(array[at],array[left]) < 0){
						T temp = array[at];
						int temp1 = index[at];
						array[at] = array[left];
						index[at] = index[left];
						array[left] = temp;
						index[left] = temp1;
						at = left;
					}
					else done = true;
				}
				else done = true;
			}
		}
		return res;
	}

	@Override
	public void add(T data) {
		// TODO Auto-generated method stub
		array[size++] = data;
		index[size-1] = size-1;
		int at = size - 1;
		int parentAt = (size-1)/2;
		while(at > 0 && array[parentAt].compareTo(array[at]) > 0 && priority(array[at],array[parentAt]) > 0){
			T temp = array[at];
			int temp1 = index[at];
			array[at] = array[parentAt];
			index[at] = index[parentAt];
			array[parentAt] = temp;
			index[parentAt] = temp1;
			int itemp = (parentAt - 1) / 2;
			at = parentAt;
			parentAt = itemp;
		}
		while(at > 0 && array[parentAt].compareTo(array[at]) < 0 && priority(array[at],array[parentAt]) > 0){
			T temp = array[at];
			int temp1 = index[at];
			array[at] = array[parentAt];
			index[at] = index[parentAt];
			array[parentAt] = temp;
			index[parentAt] = temp1;
			int itemp = (parentAt - 1) / 2;
			at = parentAt;
			parentAt = itemp;
		}
	}

	@Override
	public void addAll(Collection<T> elements) {
		// TODO Auto-generated method stub
		List<T> a = new ArrayList<T>();
		a.addAll(elements);
		for(int i=0; i<elements.size(); i++){
			if(a.get(i) == null) break;
			add(a.get(i));
		}
	}

	// do not modify methods below this point, they are for grading purposes

	@Override
	public T[] getArray() {
		return array;
	}

	@Override
	public void setArray(T[] array) {
		this.array = array;
	}

	@Override
	public void setSize(int size) {
		this.size = size;
	}
}


interface HeapInterface<T extends Comparable<T>> {

	/**
	 * @return If the heap has elements in it
	 */
	public boolean isEmpty();
	
	/**
	 * @return The number of elements in the heap
	 */
	public int size();
	
	/**
	 * Returns the element in the heap with the highest priority
	 * 
	 * @return the element with highest priority
	 */
	public T getFirst();
	
	/**
	 * Removes and returns the element in the heap with the highest priority
	 * 
	 * @return the element with highest priority
	 */
	public T remove();
	
	/**
	 * Inserts an element into the proper place in the array based on its priority
	 * 
	 * @param data The data to be inserted into the heap
	 */
	public void add(T data);
	
	/**
	 * Inserts all of the elements in a Collection into the heap
	 * 
	 * @param elements Collection with the elements to be added to the heap
	 */
	public void addAll(Collection<T> elements);
	
	// Used for grading
	public T[] getArray();
	public void setArray(T[] array);
	public void setSize(int size);
	
}

class MaxHeap<T extends Comparable<T>> extends Heap<T> {

	/**
	 * Takes in two Comparable objects to find which has higher priority
	 * 
	 * @param one An element to be prioritized  
	 * @param two An element to be prioritized
	 * @return  a positive value if parameter one is greater then parameter two,
	 * 			zero if compareTo returns zero,
	 * 			a negative value if parameter two is greater then parameter one
	 */
	public MaxHeap(){
		super();
	}
	public MaxHeap(int capacity){
		super(capacity);
	}
	@Override
	public int priority(T one, T two) {
		if(one.compareTo(two) > 0){
			return 1;
		}
		else if(one.compareTo(two) <0){
			return -1;
		}
		else return 0;
	}
}


class MinHeap<T extends Comparable<T>> extends Heap<T> {

	/**
	 * Takes in two Comparable objects to find which has higher priority
	 * 
	 * @param one An element to be prioritized  
	 * @param two An element to be prioritized
	 * @return  a negative value if parameter one is greater then parameter two,
	 * 			zero if compareTo returns zero,
	 * 			a positive value if parameter two is greater then parameter one
	 */
	public MinHeap(){
		super();
	}
	public MinHeap(int capacity){
		super(capacity);
	}
	@Override
	public int priority(T one, T two) {
		if(one.compareTo(two) > 0){
			return -1;
		}
		else if(one.compareTo(two) <0){
			return 1;
		}
		else return 0;
	}

}
bupjae 6년 전 0

Java의 Scanner는 입력 속도가 *매우* 느린 것으로 악명이 높습니다.
이 정도 규모의 입력을 처리할 때는 BufferedReader 를 추천합니다
skqjacks 6년 전 0

아.......... 감사합니다...... ㅎㅎ
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

이문제 java로 풀었을때 질문입니다.

skqjacks 6년 전 0

bupjae 6년 전 0

skqjacks 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말
