[BOJ/Java] 15654. N과 M (5)

[BOJ/Java] 15654. N과 M (5)

15654번: N과 M (5)

---

문제 해석

이 문제에서는 N개의 서로 다른 수가 주어지고, 이 수들 중에서 M개를 뽑아 나열하는 모든 경우를 사전 순으로 출력해야 한다. 이는 순열을 구하는 문제의 한 형태이다.

풀이 과정

• 입력 받기: N개의 수를 입력 받은 후 배열에 저장하고 정렬한다.
• 조합 함수: 조합을 구현하는 함수 combination을 사용하여, 선택된 숫자가 다시 선택되지 않도록 관리한다.
• 순열 생성: 사전 순으로 출력하기 위해 입력받은 숫자를 먼저 정렬한 후, 순열을 생성한다.

코드

package edu.ssafy.im.BOJ.Silver.S3.No15654;

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

public class Main {
	private static int N;  // 입력받을 숫자의 개수
	private static int M;  // 선택할 숫자의 개수
	private static int[] arr;  // 입력받은 숫자를 저장할 배열
	private static StringBuilder sb = new StringBuilder();  // 결과를 저장할 StringBuilder
	private static int[] sel;  // 선택된 숫자를 저장할 배열

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());  // 숫자의 개수 입력 받기
		M = Integer.parseInt(st.nextToken());  // 선택할 숫자의 개수 입력 받기

		arr = new int[N];  // 숫자 배열 초기화
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());  // 숫자 입력 받기
		}
		Arrays.sort(arr);  // 사전 순 출력을 위해 배열 정렬
		
		sel = new int[M];  // 선택된 숫자를 저장할 배열 초기화
		combination(0, 0);  // 조합 시작
		bw.write(sb.toString());  // 결과 출력
		bw.flush();
		bw.close();
	}

	private static void combination(int k, int v) {
		if (k == M) {  // M개를 모두 선택했을 때
			for (int i = 0; i < M; i++)
				sb.append(sel[i]).append(" ");  // 선택된 숫자를 문자열로 추가
			sb.append("\n");
			return;
		}

		for (int i = 0; i < N; i++) {
			if ((v & (1 << i)) == 0) {  // 아직 선택되지 않은 숫자라면
				sel[k] = arr[i];  // 선택 배열에 저장
				combination(k + 1, v | 1 << i);  // 다음 숫자 선택
			}
		}
	}
}

시간 복잡도 분석

이 문제에서의 시간 복잡도는 모든 순열을 생성해야 하므로, 최악의 경우 𝑂(𝑁!)가 될 수 있다.

느낀점

이 문제를 통해 순열을 생성하는 기본적인 방법과 백트래킹을 활용하여 효율적으로 모든 경우의 수를 탐색하는 방법을 다시 한 번 실습할 수 있었다. 이러한 문제는 알고리즘 공부에 있어 기본적이면서도 매우 중요한 주제로 다양한 문제 해결 방식을 익히는 데 도움이 된다.