코드트리 [자바 java] N개중에 M개 뽑기

https://www.codetree.ai/missions/2/problems/n-choose-m?utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

이 문제는 조합을 구해야 한다. 앞선 문제에서는 전부 숫자들의 순서, 중복 여부가 크게 중요하지 않았지만, 여기서는 숫자들이 오름차순으로 정렬되어야 하고 중복 되어서는 안된다.

 

import java.io.*;
import java.util.*;


public class Main {
    static int n;
    static int m;
    static int[] arr;
  


    static void func(int k, int num){ //k를 파라미터로 전달해서 for문의 시작점으로 정함
        if(num == n){
            for(int i =0 ;i<n;i++){
                System.out.printf("%d ",arr[i]);//배열이 모두 차면 출력
            }
            System.out.println();
        }
        else{
            for(int i = k;i<=m;i++){// 탐색중인 배열에 수 넣기(파라미터에서 받은 수부터 시작)
                arr[num] = i; 
                func(i+1,num+1);//다음 배열이 현재 수보다 커야하니까 i+1을 k에대한 파라미터로 전달
            }
        }
    }

  public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new int[n];

        func(1,0); // 첫 배열의 for문은 1부터 시작

    }
}

 

여기서는 func함수의 파라미터가 하나 추가된다. 이렇게 하면 현재 탐색중인 인덱스의 앞 인덱스보다 큰 수를 배정할 수가 없게 되어 자동적으로 오름차순 정렬이 된다. 또한 i+1을 k에 대한 파라미터로 전달함으로서 중복을 방지한다.

 

또한,

4자리 이진수	1-4에서 3개 뽑아 오름차순 정렬
0001	123
0010	124
0100	134
1000	234

이렇게 이진수로 만들고, 0의 위치를 출력하는 방법도 존재한다.