[백준 15656, Java] N과 M (7)

문제

www.acmicpc.net/problem/15656

15656번: N과 M (7)

 

풀이

 N과 M(3)과 같은 비슷한 문제인데 N과 M(3)과 다른 점은 (3)은 1~N까지의 숫자를 선택하는 문제이고, (7)은 0~ N-1까지의 인덱스에 있는 숫자를 선택하는 문제이다. 출력을 사전순으로 하라고 했으므로, 숫자를 입력받은 후 오름차순으로 정렬한 다음에 인덱스를 차례로 선택하면 된다. 

 

 numArray의 index에 들어갈 수 있는 숫자는  candidates 배열의 0~ 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[] candidate;
    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());

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


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

        Arrays.sort(candidate);
        pickNums(0, bw);

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

    // numArray의 index에 candiate에 있는 숫자를 넣는다. 이때 같은 수를 여러번 선택할 수 없다
    public static void pickNums(int index, BufferedWriter bw) throws Exception{
        if(index >= M ){
            for(int num :numArray){
                bw.write(String.valueOf(num)+" ");
            }
            bw.write("\n");
        }
        else{
            for(int i = 0; i<N; i++){
                int candidateNum = candidate[i];
                numArray[index] = candidateNum;
                pickNums(index+1, bw);
            }
        }
    }
}