[백준 15650, 자바] N과 M (2)

문제

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

방법1

• 크기가 M인 numArray를 선언한다

• numArray의 index에 1~N 중 하나의 숫자를 넣는다

• numArray의 index+1 에 numArray[index-1]~N 중 하나의 숫자를 넣는다. 

코드1 

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

public class Main {
    public static int N;
    public static int M;
    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());

        /*
            1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
            고른 수열은 오름차순이어야 한다.
         */

        numArray = new int[M];
        pickNum1(0, 1);
    }
    public static void pickNum1(int index, int startNum){
        if(index>=M){
            for(int num : numArray){
                System.out.print(num+" ");
            }
            System.out.println();
        }
        else if(startNum>N){
            return;
        }
        else{
            for(int num = startNum; num <= N ;num++){
                numArray[index] = num;
                pickNum1(index+1, num+1);
            }
        }
    }
}

 

방법2

• 크기가 M인 numArray를 선언한다

• 1~N 까지 숫자를 index에 넣는다, 넣지 않는다를 재귀로 구현한다

코드2

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

public class Main {
    public static int N;
    public static int M;
    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());

        /*
            1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
            고른 수열은 오름차순이어야 한다.
         */

        numArray = new int[M];
        pickNum2(1, 0);
    }
    public static void pickNum2(int num,int index){
        if(index>=M){
            for(int n : numArray){
                System.out.print(n+" ");
            }
            System.out.println();
        }
        else if(num>N){
            return;
        }
        else {
            //num을 선택한다
            numArray[index] = num;
            pickNum2(num+1, index+1);

            //num을 선택하지 않는다
            pickNum2(num+1, index);
        }

    }
}

 

예전 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main{
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws IOException {
		String[] line = br.readLine().split(" ");
		int N = Integer.parseInt(line[0]);
		int M = Integer.parseInt(line[1]);
		
		ArrayList<Integer> candidate = new ArrayList<Integer>();
		NM1(candidate,N,M);
		bw.close();
		

	}
	
	public static void NM1(ArrayList<Integer> candidate, int N, int M) throws IOException {
		if(candidate.size()>=M) {
			for(int i=0;i<candidate.size();i++) {
				bw.write(Integer.toString(candidate.get(i))+" ");
			}
			bw.write("\n");

		}
		else {
			for(int num =1 ; num<=N ; num++) {
				if(isPromising(num,candidate)) {
					candidate.add(num);
					NM1(candidate,N,M);
					candidate.remove(candidate.size()-1);
				}
			}
		}
	}
	public static boolean isPromising(int num, ArrayList<Integer>candidate) {
		for(int i=0;i<candidate.size();i++) {
			if(num == candidate.get(i)) {
				return false;
			}
			if(num<candidate.get(i)) {
				return false;
			}
		}
		return true;
	}


}

 

 

2020.07.27 코드수정

package may12;

import java.io.BufferedReader;
import java.util.Scanner;

class NM {
    int N;
    int M;
    boolean[] isExist;
    int[] array;

    NM(int N, int M) {
        this.N = N;
        this.M = M;
        isExist = new boolean[N + 1];
        array = new int[M];
    }

    void getNumArray1(int index) {
        if (index >= array.length) {
            //출력
            for (int num : array) {
                System.out.print(num + " ");
            }
            System.out.println();
        } else {
            for (int num = 1; num <= N; num++) {
                if (!isExist[num]) {
                    isExist[num] = true;
                    array[index] = num;
                    getNumArray1(index + 1);
                    isExist[num] = false;
                }
            }
        }
    }

    void getNumArray2(int index, int startNum) {
        if (index >= array.length) {
            //출력
            for (int num : array) {
                System.out.print(num + " ");
            }
            System.out.println();
        } else {
            for (int num = startNum; num <= N; num++) {
                if (!isExist[num]) {
                    isExist[num] = true;
                    array[index]=num;
                    getNumArray2(index + 1, num + 1);
                    isExist[num] = false;
                }
            }
        }
    }
}
public class NM1Demo {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N= in.nextInt();
        int M= in.nextInt();

        NM nm2 = new NM(N,M);

        nm2.getNumArray2(0,1);
    }

}