[알고리즘] 분할 정복 예제

ex)오름차순으로 정렬된,  중복이 없는 정수열로부터, 크기가 3인 모든 부분집합을 출력하는 프로그램을 작성하시오. 부분집합들은 사전 오름차순으로 출력되어야 합니다. 세 숫자 중 첫 숫자가 가장 작은 부분집합이 먼저 출력되어야 하고, 첫 숫자가 같은 두 부분집합 중에는 두 번째 숫자가 더 작은 부분집합이 먼저 출력되어야 합니다.

<입력>

오름차순으로 정렬된, 중복이 없는, 정수열 한 줄

<출력>

크기가 3인 모든 부분집합들을 한 줄에 하나씩 출력한다.

package hi;
import java.util.Scanner;
class Main2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		String a[] = str.split(" ");
		int[] ans = new int[a.length];
		for(int i=0; i<a.length; i++) {
			ans[i] = Integer.parseInt(a[i]);
		}
		int rV[] = getMaxMin(ans);
		System.out.print("[" +rV[0] + ", " + rV[1] + "]");
	}
	public static int[] getMaxMin(int input[]){
		int returnValue[]=new int[2];
		returnValue[0]=Integer.MAX_VALUE;//최소
		returnValue[1]=Integer.MIN_VALUE;//최대

		if(input.length%2==0){	//배열의 개수가 짝수일 때
			for(int i=0; i<input.length; i+=2){
				if(input[i]>input[i+1]){	
					int temp=input[i];
					input[i]=input[i+1];	//input[i]에 작은 값 input[i+1]에 큰 값
					input[i+1]=temp;
				}
				if(returnValue[0]>input[i]){	//returnValue[0]최소값이 input[i]의 작은 값보다 크다면 교환
					returnValue[0]=input[i];
				}    
				if(returnValue[1]<input[i+1]){ //returnValue[1]최대값이 input[i+1]의 큰 값보다 크다면 교환
					returnValue[1]=input[i+1];
				}    
			}
		}
		else{	//배열의 개수가 홀수일 때
			for(int i=0; i<input.length-2; i+=2){
				if(input[i]>input[i+1]){
					int temp=input[i];
					input[i]=input[i+1];
					input[i+1]=temp;
				}
				if(returnValue[0]>input[i]){
					returnValue[0]=input[i];
				} 
				if(returnValue[1]<input[i+1]){
					returnValue[1]=input[i+1];
				} 

			}
		}
		return returnValue;
	}

}