개발자가 되기 위한 첫 걸음

앞에서 만들었다가 크게 효율에 영향을 주지 않는 것 같아 뺐던 fastcheck의 아이디어를 이용하면

fastcheck가 안되면, 짧은 pipe의 list중에서 가장 긴 것부터 순서대로 하나씩 빼서 긴 pipe의 총합보다 작아질때까지 제한 후에 프로세스를 진행해야 한다.

더 짧은 pipe를 빼내는 것은 항상 비효율적이기 때문. (설명이 장황하여 생략, 조금만 생각하면...)

그 이후에 그냥 recursion을 이용해도 되고, 아니면 새로운 아이디어를 적용해 볼 수 있을 것.

잠깐 떠오른 아이디어는, 일단 짧은 파이프의 합이 긴 파이프 하나보다 작은 동안 짧은 파이프를 긴 파이프에 대응시키고 

남는 것은 모조리 맨 뒤의 파이프에 대응시킨 후에

짧은 파이프가 대응되는 값인, 앞의 짧은 파이프 갯수+맨 뒤의 짧은 파이프에서 긴것 몇 개를 빼낸 것

을 최대화하는 방향으로 교환을 만들어가면 될 것 같기도 하다.

여기서 교환의 과정을 잘 만들어야 하기 때문에 생각을 좀 더 정리해야 할 듯 하고

일단 fastcheck를 부활시켜서 짧은 파이프를 제하는 것을 고려하면 될 듯.

훨씬 나아졌지만, 아직 시간이 오래 걸림

package defaultpackage;

import java.util.Arrays;

public class Pipe implements Cloneable{
	int[] longPipe;
	int[][] shortPipe=new int[2][];
	
	
	//constructor
	public Pipe(int[] longPipe, int[] shortPipe) {
		this.longPipe=longPipe;
		this.shortPipe[0]=shortPipe;
		this.shortPipe[1]=new int[shortPipe.length];
		for(int i=0;i<shortPipe.length;i++) 		// shortPipe가 해결되지 않은 경우 2nd arg를 -1로 set
			this.shortPipe[1][i]=-1;
	}

	
	public int maximizer(int curNumOfPipe, int max) {
		int l=longPipe.length, s=shortPipe[0].length;
		int maxNumOfPipe=curNumOfPipe;
		for(int i=0;i<s;i++) { 								//i번째 shortPipe를 잘라낼 수 있는지 하나씩 확인하려 함
			if(curNumOfPipe+s-i<=max)
				break;
			if(shortPipe[1][i]==-1) {						//i번째 shotrPipe가 처리되지 않은 파이프(-1)일 때만 자르는 과정 수행
				for(int j=0;j<l;j++) {						//longPipe중 shortPipe를 잘라낼 수 있는 j번째 longPipe를 찾음
					int compare=longPipe[j];				//j번째 longPipe에서 이미 잘라낸 양을 제해주기 위한 계산
					for(int k=0;k<s;k++) {
						if(shortPipe[1][k]==j)				//j번째 longPipe에서 제해 준 shortPipe를 골라 long에서 뺌
							compare-=shortPipe[0][k];
					}
					if(compare>=shortPipe[0][i]) {
						shortPipe[1][i]=j;
						int n=this.maximizer(curNumOfPipe+1,maxNumOfPipe);
						if(maxNumOfPipe<n)
							maxNumOfPipe=n;
						shortPipe[1][i]=-1;
					}
				}
			}
		}
		return maxNumOfPipe;
	}

	
	public static void main(String[] args) {
		int M=Integer.parseInt(args[0]);
		int[] longPipe=new int[M];
		for(int i=0;i<M;i++)
			longPipe[i]=Integer.parseInt(args[i+1]);
		int N=Integer.parseInt(args[M+1]);
		int[] shortPipe=new int[N];
		for(int i=0;i<N;i++)
			shortPipe[i]=Integer.parseInt(args[M+i+2]);

		long start=System.currentTimeMillis();
		Arrays.sort(longPipe);
		Arrays.sort(shortPipe);
		
		Pipe pipe=new Pipe(longPipe,shortPipe);
		System.out.println(pipe.maximizer(0,0));
		System.out.println((System.currentTimeMillis()-start)/1000.0);
	}
}

clone을 더 이상 사용하지 않고 temporary integer를 이용하여 해결하였으나 여전히 성능 개선이 되지 않는 중.

최악의 경우를 상정하면 분명 모든 경우를 다 체크해야 하는게 맞다. 

그러나 끝까지 체크해 보지 않더라도 중간 쯤에서 더 이상 계산하지 않아도 되는 지점에서 break를 걸 수 있으면 좋을 텐데.

일단 코드를 올린 후에 current maximum도 인자로 넘겨서 체크하는 것을 추가해서

끝까지 계산하지 않아도 되로록 수정해봐야겠다.

package defaultpackage;

import java.util.Arrays;

public class Pipe implements Cloneable{
	int[] longPipe;
	int[][] shortPipe=new int[2][];
	
	public Pipe(int[] longPipe, int[] shortPipe) {
		this.longPipe=longPipe;
		this.shortPipe[0]=shortPipe;
		this.shortPipe[1]=new int[shortPipe.length];
		for(int i=0;i<shortPipe.length;i++)
			this.shortPipe[1][i]=-1;
	}

	public int maximizer(int curNumOfPipe) {
		int l=longPipe.length, s=shortPipe[0].length;
		int maxNumOfPipe=curNumOfPipe;
		for(int i=0;i<s;i++) { 								//i번째 shortPipe를 잘라낼 수 있는지 하나씩 확인하려 함
			if(shortPipe[1][i]==-1) {						//i번째 shotrPipe가 처리되지 않은 파이프(-1)일 때만 자르는 과정 수행
				for(int j=0;j<l;j++) {						//longPipe중 shortPipe를 잘라낼 수 있는 j번째 longPipe를 찾음
					int compare=longPipe[j];				//j번째 longPipe에서 이미 잘라낸 양을 제해주기 위한 계산
					for(int k=0;k<s;k++) {
						if(shortPipe[1][k]==j)				//j번째 longPipe에서 제해 준 shortPipe를 골라 long에서 뺌
							compare-=shortPipe[0][k];
					}
					if(compare>=shortPipe[0][i]) {
						shortPipe[1][i]=j;
						int n=this.maximizer(curNumOfPipe+1);
						if(maxNumOfPipe<n)
							maxNumOfPipe=n;
						shortPipe[1][i]=-1;
					}
				}
			}
		}
		return maxNumOfPipe;
	}

	public static void main(String[] args) {
		int M=Integer.parseInt(args[0]);
		int[] longPipe=new int[M];
		for(int i=0;i<M;i++)
			longPipe[i]=Integer.parseInt(args[i+1]);
		int N=Integer.parseInt(args[M+1]);
		int[] shortPipe=new int[N];
		for(int i=0;i<N;i++)
			shortPipe[i]=Integer.parseInt(args[M+i+2]);

		long start=System.currentTimeMillis();
		Arrays.sort(longPipe);
		Arrays.sort(shortPipe);
		
		Pipe pipe=new Pipe(longPipe,shortPipe);
		System.out.println(pipe.maximizer(0));
		System.out.println((System.currentTimeMillis()-start)/1000.0);
	}
}

조금 수정한 코드.

복사를 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);
	}
}

M개의 긴 파이프의 숫자와 길이가 주어지고 N개의 짧은 파이프의 숫자와 길이가 주어질 때

N개의 파이프 중 만들 수 있는 최댓값을 구하는 문제이다.

인풋, 아웃풋은 txt파일을 수정해야 해서 class내에서 random함수를 돌려 파이프의 갯수와 길이를 생성하도록 하였다.

문제는, return값이 계속 1이 나온다는 것인데

중간값을 모조리 출력해 보니 최댓값이 잘 증가하다가 마지막에 내리막을 타고 1까지 다시 감소하고 있다.

실제 변수들을 써가면서 따라가봐야 할 것 같다.

코드의 어느 부분이 잘못되었는지 아직 발견하지 못하는 중

아래는 결과가 제대로 출력되지 않는 코드.

public class Pipe {
	int[] longPipe, shortPipe;
	
	public Pipe(int[] longPipe, int[] shortPipe) {
		this.longPipe=longPipe;
		this.shortPipe=shortPipe;
	}
	
	public Pipe gotOneFromLong (Pipe pipe, int i, int j) {
		pipe.longPipe[i]=pipe.longPipe[i]-pipe.shortPipe[j];
		pipe.shortPipe[j]=0;
		return pipe;
	}
	
	public int maximizePipe(Pipe pipe, int numberOfCurrentPipe) {
		int l=pipe.longPipe.length, s=pipe.shortPipe.length;
		int maxNumOfPipe=numberOfCurrentPipe;
		for(int i=0;i<l;i++) {
			for(int j=0;j<s;j++) {
				if(pipe.shortPipe[j]==0 || pipe.longPipe[i]<pipe.shortPipe[j])
					continue;
				if(maxNumOfPipe<maximizePipe(gotOneFromLong(pipe,i,j),numberOfCurrentPipe+1))
					maxNumOfPipe=maximizePipe(gotOneFromLong(pipe,i,j),numberOfCurrentPipe+1);
			}
		}
		return maxNumOfPipe;
	}
	
	public static void main(String[] args) {
		long start=System.currentTimeMillis();
		int numOfLong, numOfShort;
		numOfLong=(int)(Math.random()*50)+1;
		numOfShort=(int)(Math.random()*1023)+1;
		int[] longPipe=new int[numOfLong], shortPipe=new int[numOfShort];
		
		for(int i=0;i<numOfLong;i++) {
			longPipe[i]=(int)(Math.random()*10000)+90000;
			System.out.printf("%d ", longPipe[i]);
		}
		System.out.println();
		for(int i=0; i<numOfShort;i++) {
			shortPipe[i]=(int)(Math.random()*128)+1;
			System.out.printf("%d ",shortPipe[i]);
		}
		System.out.println();
		
		
		Pipe pipe=new Pipe(longPipe, shortPipe);
		System.out.println(pipe.maximizePipe(pipe, 0));
		System.out.println((System.currentTimeMillis()-start)/1000.0);
	}
}