[백준] 6603 로또

문제보기

1. 재귀로 푸는 경우

import java.util.*;

// k < 13 이라 2^13 = 8000좀 넘나? 암튼 재귀로 충분히 가능 
public class Main {
  public static List<Integer> list;
  public static void go(int[] arr, int idx, int cnt){
    if(cnt == 6){ // 종료 조건
      for(int i = 0 ; i < 6 ; i++){
        System.out.print(list.get(i) + " "); // 모은 거 모두 출력하자
      }System.out.println();
      return;
    }
    if(idx >= arr.length){ // 채운것도 없으면서 Idx만 커진경우 -> 종료
      return;
    }

    list.add(arr[idx]); // 현재 인덱스 값 집어넣기
    go(arr, idx+1, cnt+1); 
		
    list.remove(cnt); // 현재 인덱스 값 안넣고 통과하기
    go(arr, idx+1, cnt);
  }

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    while(n != 0){
      list = new ArrayList<Integer>();

      int[] arr = new int[n];
      for(int i = 0 ; i < n ; i++){
        arr[i] = sc.nextInt();
      }
      go(arr, 0, 0);
      System.out.println();
      n = sc.nextInt();
    }

  }
}

1. 순열로 푸는 경우

import java.util.*;

public class Main {

  // 순열로 조합문제를 푸는 경우의 대표적인 유형이다
  // 선택함&선택안함의 조건을 담는 배열을 새로 만들어서 걔로 다음순열(혹은 이전순열) 만들어가며 선택여부를 결정해주면 된다.
  
  // 이전 순열 찾아주는 메서드 - 원리는 다음 순열 포스팅을 참고
  public static boolean next_perm(int[] arr){
    int i = arr.length -1; 
    while( i > 0 && arr[i-1] <= arr[i]){
      i--;
    }
    if(i <= 0){
      return false; 
    }
    int j = arr.length -1; 
    while( arr[j] >= arr[i-1] ){
      j--;
    }

    int temp = arr[j];
    arr[j] = arr[i-1];
    arr[i-1] = temp;

    int k = arr.length -1;
    while( i < k ){
      temp = arr[k];
      arr[k] = arr[i];
      arr[i] = temp;
      i++;
      k--;
    }
    return true; 
  }


  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    while(n != 0 ){

      int[] nums = new int[n];
      for(int i = 0 ; i < n ; i++ ){
        nums[i] = sc.nextInt();
      }

      Arrays.sort(nums);

      int[] sel = new int[n];
      // sel 배열의 초기값 : {1, 1, 1, 1, 1, 1, 0, 0, ...}
      // 1이면 해당 인덱스의 nums를 선택, 0이면 선택하지 않음 
      for(int i = 0 ; i < 6 ; i++){
        sel[i] = 1;
      }
      for(int i = 6 ; i < n ; i++){
        sel[i] = 0;
      }
  


      do{
        for(int i = 0 ; i < n ; i++ ){
          if(sel[i]==1){ // 선택하는 경우는 출력 
            System.out.print(nums[i] + " ");
          }
        }
        System.out.println();

      }while(next_perm(sel));
      System.out.println();
      n = sc.nextInt();
    }
  }
}