백준:Pipe 자르기2

조금 수정한 코드.

복사를 deep copy로 수정하고, 빠르게 check하는 알고리즘을 한 군데 추가.

하지만 여전히 실행 속도가 느림.

최악의 경우에도 효율이 좋은 방향을 찾아야 함.

package defaultpackage;

public class Pipe implements Cloneable{
	int[] longPipe, shortPipe;
	
	public Pipe(int[] longPipe, int[] shortPipe) {
		this.longPipe=longPipe;
		this.shortPipe=shortPipe;
	}
	
	public int arraySum(int[] array) {
		int sum=0;
		for(int temp:array)
			sum+=temp;
		return sum;
	}
	
	
	// the input array is treated a sorted one find the first nonzero location 
	public int countNonZero(int[] array) {
		int counter=0;
		for(int temp:array) {
			counter++;
			if(temp!=0)
				return array.length-counter;
		}
		return counter;
	}
	public Pipe clone() {
		return new Pipe(longPipe.clone(),shortPipe.clone());
	}
	
	public void print() {
		int sum1=0, sum2=0;
		for(int temp:longPipe) {
			System.out.printf("%d ", temp);
			sum1+=temp;
		}
		System.out.println();
		for(int temp2:shortPipe) {
			System.out.printf("%d ", temp2);
			sum2+=temp2;
		}
		System.out.printf("%n==============%n");
		System.out.printf("Long: %d, Short: %d",sum1,sum2);
	}
	
	public boolean fastCheck() {
		if(arraySum(longPipe)<arraySum(shortPipe))
			return false;
		int l=longPipe.length, s=shortPipe.length;
		int counter=0;
		for(int i=0;i<s;i++) {
			for(int j=0;j<l;j++) {
				if(longPipe[j]>=shortPipe[i]) {
					longPipe[j]=longPipe[j]-shortPipe[i];
					counter++;
					break;
				}
			}
		}
		return counter==shortPipe.length;
	}
	
	public int maximizer(int curNumOfPipe) {
		int l=longPipe.length, s=shortPipe.length;
		int maxNumOfPipe=curNumOfPipe;
		int temp=0;
		Pipe copy=this.clone();
		if(copy.fastCheck())
			return shortPipe.length;
		copy=this.clone();
		for(int i=0;i<l;i++) {
			for(int j=0;j<s;j++) {
				if(shortPipe[j]!=0 && longPipe[i]>=shortPipe[j]) {
					copy.longPipe[i]=copy.longPipe[i]-copy.shortPipe[j];
					copy.shortPipe[j]=0;
					temp=copy.maximizer(curNumOfPipe+1);
					if(maxNumOfPipe<temp)
						maxNumOfPipe=temp;
					copy.longPipe[i]=copy.longPipe[i]+shortPipe[j];
					copy.shortPipe[j]=shortPipe[j];
				}
			}
		}
		return maxNumOfPipe;
	}
	
	public static void main(String[] args) {
		int numOfLong, numOfShort;
		Sort s=new Sort();

		numOfLong=(int)(Math.random()*50)+1;
		numOfShort=(int)(Math.random()*100)+1;

		int[] longPipe=new int[numOfLong], shortPipe=new int[numOfShort];
		
		for(int i=0;i<numOfLong;i++)
			longPipe[i]=(int)(Math.random()*1000);
		for(int i=0; i<numOfShort;i++)
			shortPipe[i]=(int)(Math.random()*128)+1;
		
		long start=System.currentTimeMillis();
		Pipe pipe=new Pipe(s.sort(longPipe), s.sort(shortPipe));
		pipe.print();
		System.out.println(pipe.maximizer(0));
		System.out.println((System.currentTimeMillis()-start)/1000.0);
	}
}