백준 - 15651 N 과 M (3)

풀이-1

import java.util.Scanner;

public class Main_15651 {//시간 초과 (중복순열은 출력되는 경우의 수가 많다)
/*
문제)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

 - 1부터 N까지 자연수 중에서 M개를 고른 수열
 ==> 같은 수를 여러 번 골라도 된다.

입력)
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.	
 */
	static int N,M;
	static int[]answer;	
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt(); //전체 데이터 개수(자연수)
		M = scan.nextInt(); //고를 수 있는 개수
		
		answer = new int[M];		
		
		permute(0); //0: 몇개를 선택했는지 표현
		
		scan.close();
    }//main

	private static void permute(int depth) {//재귀함수
		//끝날 조건
		if(depth == M) { //선택을 끝마쳤을때
			for(int num : answer){//선택데이터 출력
				System.out.print(num+" ");
			}
			System.out.println();
		   
		  return;//끝마쳐!! (나를 호출한 메서드에게 제어권 넘기기)
		}
		
	   //반복 처리문	
	   for(int i=1; i<=N; i++){//선택할 수 있는 요소에 대한 표현			  
			  answer[depth]=i;//선택해!! i는 자연수를 의미	
	          permute(depth+1); //다음 선택을 표현
	   }
	}//permute
}

 

풀이-2

import java.util.Scanner;

public class Main_15651_v2 {//시간 초과 (중복순열은 출력되는 경우의 수가 많다)
/*
문제)
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

 - 1부터 N까지 자연수 중에서 M개를 고른 수열
 ==> 같은 수를 여러 번 골라도 된다.

입력)
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.	
 */
	static int N,M;
	static int[]answer;	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt(); //전체 데이터 개수(자연수)
		M = scan.nextInt(); //고를 수 있는 개수
		
		answer = new int[M];		
		
		permute(0); //0: 몇개를 선택했는지 표현
		
		//출력은 한번만!
		System.out.print(sb.toString());
		
		scan.close();
    }//main

	private static void permute(int depth) {//재귀함수
		//끝날 조건
		if(depth == M) { //선택을 끝마쳤을때
			for(int num : answer){//선택데이터 출력
				sb.append(num)
				  .append(' ');
			}
			sb.append('\n');
		   
		  return;//끝마쳐!! (나를 호출한 메서드에게 제어권 넘기기)
		}
		
	   //반복 처리문	
	   for(int i=1; i<=N; i++){//선택할 수 있는 요소에 대한 표현			  
			  answer[depth]=i;//선택해!! i는 자연수를 의미	
	          permute(depth+1); //다음 선택을 표현
	   }
	}//permute
}