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

---

문제 설명

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

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

출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

---

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
 * N개중에서 R개 뽑기
 * _,_,_이 있을 때 3개 뽑는다면
 * 1,_,_ 와 2,_,_ 와 3,_,_ ... N,_,_
 * 그다음 1,2_ 와 1,3,_ 와 1,4,_와... 1,N,_
 * ....
 * N,N-1,N-2
 * */
public class Main {
	static int N;
	static int R;
	static int[] result;
	static boolean[] used;
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		result = new int[R];
		used = new boolean[N+1];
		
		perm(0); //result의 0번 인덱스부터 값을 채우도록
		System.out.println(sb);
	}
	static void perm(int idx) {
		if (idx==R) { //만약 idx가 결국 R의 위치에 있으면(순열이 다 만들어짐)
			for (int n : result) {
				sb.append(n+" ");
			}
			sb.append("\n");
			return;
		}
		
		for (int i = 1; i <= N; i++) { //순열 재료는 1부터 N
			if (used[i]) continue; //만약 지금 숫자가 순열에 쓰였으면 넘어가기
			
			result[idx] = i; //현재 인덱스에 숫자 넣기
			used[i] = true; //숫자가 쓰임
			perm(idx+1); //다음 인덱스부터 값을 채우도록 함
			used[i] = false; //현재 인덱스에 다른 숫자를 넣는 순열을 만들어야 하므로 현재 숫자는 안쓰인걸로 바꿈
		}
	}
}

오늘 재귀함수를 배우고 풀어본 문제이다.

1. 만약 1,2,3,4중에서 3자리 순열을 만들어야 한다면 첫 번째 자리는 1,2,3,4가 올 수 있다.
2. 첫 번째 자리가 1이 오면 그 다음 자리는 1을 제외한 2,3,4가 올 수 있다.
3. 그 다음 자리는 1,2를 제외한 3,4가 올 수 있다.

한 자리 숫자를 결정하는 함수를 재귀함수로 만들어 재귀호출하면 된다.

for문을 돌리며 각 자리에 재료(for문의 i)가 들어갈 수 있는지 검사한다.

들어갈 수 있다면 reuslt의 현재 자리에 i값을 넣는다.

그리고 그 재료를 못쓰게 한다.

마지막으로 다음 자리의 숫자 결정을 후배 재귀perm(idx+1)에게 미룬다.

후배 재귀들이 숫자 결정을 전부 했다면 재료를 사용할 수 있게 한다.

---

결과

---

내가 과거에 쓴 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static int[] arr;
	public static boolean[] visit;
	public static StringBuilder sb = new StringBuilder();
	public static int N, M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		arr = new int[M];
		visit = new boolean[N];
		dfs(0);
		System.out.println(sb);
	}
	public static void dfs(int depth) {
		if (depth == M) {
			for (int val : arr) {
				sb.append(val).append(' ');
			}
			sb.append('\n');
			return;
		}
		for (int i = 0; i < N; i++) { //dfs(0)일 땐 앞 자리 결정
			if (visit[i] == false) { //해당 인덱스 값을 썼는가?
				/* i가 0이라면 1을 썼냐고 묻는 것 */
				visit[i] = true; //썼다고 표시 후
				arr[depth] = i + 1; //수열의 앞 숫자 결정(i가 0이면 1)
				dfs(depth + 1); //앞 숫자 결정된 수열에 대한 dfs
				visit[i] = false; //다음 순번(i가 1일때)를 위한 처리
			}
		}
		return;
	}
}

과거의 나..어떻게 한 거냐?!

로직은 똑같은데 왜 사용 공간도 적고 속도도 빠른 걸까..?

설마 used(=visit)의 크기가 고작 1 차이나는 것 때문에?!!
확인해봤는데 아님..