조합[NextPermution][Java]

[광고 누르면 오늘의 행운 상승!!]

 

조합을 생성하는 또 다른 방법.

package Study0307;

import java.util.Arrays;
import java.util.Scanner;

public class Combination {

   static int N;
   static int[] input;
   static int totalCnt;
   
   public static void main(String[] args) {
      Scanner sc=new Scanner(System.in);
      N=sc.nextInt();
      input=new int[N];
      for(int i=0; i<N; i++) {
         input[i]=sc.nextInt();
      }
      
      //시작: 가장 작은 순열
      Arrays.sort(input);
      do {
         System.out.println(Arrays.toString(input));
      }while(nextPermution());
      System.out.println("총경우의 수: "+totalCnt);
   }
   
   private static boolean nextPermution() {
      totalCnt++;
      //step1
      int i=N-1;
      while(i>0 && input[i-1]>=input[i]) i--;
      if(i==0) return false;
      
      //step2
      int j=N-1;
      while(input[i-1]>=input[j]) j--;
      
      //step3
      int temp=input[i-1];
      input[i-1]=input[j];
      input[j]=temp;
      
      //step4
      int k=N-1;
      while(i<k) {
         temp=input[i];
         input[i]=input[k];
         input[k]=temp;
         i++;
         k--;
      }
      return true;
      
   }

}