[백준 알고리즘 - 6603] 로또 -java(중복된 수가 있는 집합의 순열) +(20180901 백트래킹 코드 추가)

중복된 수가 있는 집합의 순열을 구할 때는 next_permutation의 비교문을 '='를 추가하기만 하면 된다.

이 문제는 크기가 k인 집합 중 6개를 뽑아서 순열을 사전식으로 출력하는 것이다.

사전식이기 때문에 새로운 배열 roto를 [0,0,0,0,0,0,1,1] 로 선언한다.

그런다음 이 배열을 처음 입력받은 크기가 k인 집합 arr과 비교하여 출력하는 것이다.

예를들어 roto[i]가 0이면 arr[i]를 선택하는 것이다. 

그렇게 출력한 뒤 roto 배열의 다음 순열을 구하고 똑같은 과정을 거치면 중복된 수가 있는 집합의 순열을 구할 수 있다.

import java.util.Scanner;
public class Main {
	public static boolean next_permutation(int[] arr){
		int s=0; int e=arr.length;
		//arr[i-1] < arr[i]를 만족하는 가장 큰 i
		int i=e-1;
		for(; i>s; i--){			
			if(arr[i-1] >=arr[i])
				continue;
			else
				break;
		}
		if(i==0) return false;

		//i<=j를 만족하고, A[j]>A[i-1]를 만족하는 가장 큰 j
		int j=e-1;
		for(; j>=i; j--){
			if(arr[j]<=arr[i-1])
				continue;
			else
				break;
		}
	
		
		//A[i-1], A[j] swap
		int tmp=arr[i-1];
		arr[i-1]=arr[j];
		arr[j]=tmp;
		//1234567
		//i부터 끝까지 뒤집음 
		j=e-1;
		while(i<j){
			int temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;
			i++; j--;
		}
		return true;
	}
	
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		boolean flag=false;
		while(true) {
			int k=scan.nextInt();
			if(k==0) return;
			int[] arr=new int[k];
		
			for(int i=0; i<k; i++)
				arr[i]=scan.nextInt();
			if(flag)
				System.out.println();
			int[] roto=new int[k];
			for(int i=0; i<k; i++) {
				if(i<6)
					roto[i]=0;
				else
					roto[i]=1;
			}
			
			do {
				for(int i=0; i<k; i++) {
					if(roto[i]==0)
						System.out.print(arr[i]+" ");
				}
				System.out.println();
				flag=true;
			}while(next_permutation(roto));
			
			
		}
	}

}

(2018-09-01 추가)

같은 문제를 백트래킹으로 구현해보았다.

두 코드의 속도는 놀랍게도 일치하는군, 개인적으로 아래 코드가 더 쉬운 것 같다.

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



class Main{
	//arr=주어진 배열, idx=현재 검사중인 인덱스, count=지금까지 채워진 인덱스, result=채우고있는 배열
	  public static void roto(int[] arr, int idx, int count, int[] result) {
		  if(idx>=arr.length && count<6) {
			  return;
		  }
		  if(count==6) {//6개 다 뽑음
			  for(int i=0; i<result.length; i++)
				  System.out.print(result[i]+" ");
			  System.out.println();
			  return;
		  }
		  
		  //현재 인덱스를 포함하는 경우
		  result[count]=arr[idx];
		  roto(arr, idx+1, count+1, result);
		  
		  //현재 인덱스를 포함하지 않는 경우
		  result[count]=0;
		  roto(arr,idx+1, count, result);
	  }
       public static void main(String[] args){
    	   Scanner scan=new Scanner(System.in);
    	   
    	   while(true) {
    		   int T=scan.nextInt();
    		   if(T==0)
    			   return;
    		   int[] arr=new int[T];
    		   for(int i=0; i<T; i++)
    			   arr[i]=scan.nextInt();
    		   
    		   int[] result=new int[6];
    		   roto(arr, 0,0, result);
    		   System.out.println();
    	   }
       }