[백준 15657, Java] N과 M (8)

문제

www.acmicpc.net/problem/15657

15657번: N과 M (8)

 

풀이

 N과 M (4)와 비슷한 문제다. (4)와 (8)의 다른 점은, (4)는 1~N까지의 숫자를 선택하는 것이고 (8)은 수열의 1(0)~N(N-1)까지의 인덱스에 있는 숫자를 선택하는 것이다. 

 

 선택할 숫자가 있는 배열을 크키가 N이고, 이름을 candidate로 선언한 후 오름차순 정렬을한다. 선택한 숫자가 있는 배열을 크기가 M이고 이름을 numArray라고 선언한다. numArray의 n번째 인덱스에 candidate의 인덱스 m에 있는 숫자를 넣는다고 하자. 그럴경우 numArray의 n+1번째 인덱스에 올 수 있는 candidate의 인덱스는 m~ N-1이다. 이를 재귀로 구현하면 된다. 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int M;
    public static int[] candidates;
    public static int[]  numArray;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        candidates = new int[N];
        numArray = new int[M];

        st = new StringTokenizer(br.readLine()," ");
        for(int index = 0 ; index<N; index++){
            candidates[index] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(candidates);
        pickNums(0, 0, bw);

        bw.flush();
        br.close();
        bw.close();

    }

    public static void pickNums(int numIndex, int candiIndex,  BufferedWriter bw)throws Exception{
        if(numIndex>=M){
            for(int num : numArray){
                bw.write(String.valueOf(num)+" ");
            }
            bw.write("\n");
        }
        else{
            for(int index = candiIndex; index <N; index++){
                numArray[numIndex] = candidates[index];
                pickNums(numIndex+1, index, bw);
            }
        }
    }
}