[Java]BOJ15649, 백준 - N과M(1)

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

15649번: N과 M (1)

문제

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

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

입력

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

 

출력

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

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

 

 

<풀이>

재귀를 이용하여 풀려고 시도하였다.

1. 함수의 종료조건: M개의 수열을 골라야 하기 때문에, 한 줄에 M개의 숫자를 출력하면 해당 함수를 종료한다.

2. 함수의 매개변수 

• boolean[] check : 해당 수를 지나쳤는지 검사
• int cnt : 지금까지 몇 개의 숫자를 출력했는지 저장
• + int[] arr : 어떤 수를 출력해야 할 지 저장

처음에는 수열을 저장할 배열을 따로 만들지 않으려고 했으나, 그러면 재귀에서 빠져나간 후에 다시 진행할 때 앞의 숫자가 비어버리는 현상이 발생하였다. 그래서 매개변수에 수열을 저장할 arr을 추가하였다.

 

1차 코드

import java.io.*;
import java.util.*;

public class Main {
	private static int n;
	private static int 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());
		boolean[] check = new boolean[n + 1];
		int[] arr = new int[n + 1];
		go(check, arr, 1);
	}

	private static void go(boolean[] check, int[] arr, int cnt) throws IOException {
		if (cnt > m) {
			for (int i = 1; i <= n; i++) {
				if (arr[i] != 0)
					System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}

		for (int j = 1; j <= n; j++) {
			if (!check[j]) {
				check[j] = true;
				arr[cnt] = j;
				go(check, arr, cnt + 1);
				check[j] = false;
			}
		}
	}
}

 

2차 코드

언제나 더 나은 코드가 존재한다

1. check배열과 arr배열을 굳이 매개변수로 전달해줄 필요가 없고, 전역변수로 사용하자. 왜? 배열은 참조 타입이기 때문에 어차피 같은 메모리를 공유한다.
2. 들여쓰기를 최소화할 수 있도록 하자(continue를 이용)
3. 출력하는 부분도 함수를 따로 만들어 사용해준다면 조금 더 가독성 높은 코드가 된다.
4. 함수 쓴다고 println으로 처리하려고 하지 말고 StringBuilder를 이용하자,, 메모리랑 시간 단축

import java.io.*;
import java.util.*;

public class Main {
	private static int n;
	private static int m;
	private static boolean[] check;
	private static int[] arr;
	private 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());
		m = Integer.parseInt(st.nextToken());
		check = new boolean[n + 1];
		arr = new int[n + 1];
		go(1);
		System.out.println(sb);
	}

	private static void go(int cnt) {
		if (cnt > m) { // 종료조건, M만큼 출력했을 때
			append();
			return;
		}

		for (int j = 1; j <= n; j++) {
			if (check[j])
				continue;
			check[j] = true;
			arr[cnt] = j;
			go(cnt + 1);
			check[j] = false;
		}
	}

	private static void append() {
		for (int i = 1; i <= n; i++) {
			if (arr[i] != 0)
				sb.append(arr[i] + " ");
		}
		sb.append("\n");
	}
}