[BOJ/Java] 15657. N과 M (8)

[BOJ/Java] 15657. N과 M (8)

15657번: N과 M (8)

---

문제 해석

이 문제는 자연수 N개 중에서 M개를 고른 수열을 모두 구하는 문제이며, 수열은 비내림차순(같거나 커지는 순서)이어야 한다. 입력된 수는 중복될 수 있으며, 수열도 중복될 수 있다.

풀이 과정

1. 입력 받기: N과 M을 입력받고, N개의 수를 배열에 저장한 뒤 정렬한다.
2. 조합 수행: 조합을 재귀적으로 수행하면서, 이미 선택한 수 이후의 수들만 선택할 수 있도록 한다. 이는 비내림차순 조건을 만족시키기 위함이다.
3. 수열 저장 및 출력: 선택된 수들을 StringBuilder에 저장하고, 최종적으로 출력한다.

코드

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

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

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

	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 start) {
		if (k == M) { // M개를 모두 선택한 경우
			for (int i = 0; i < M; i++)
				sb.append(sel[i]).append(" ");
			sb.append("\n");
			return;
		}

		for (int i = start; i < N; i++) { // 이전에 선택한 수의 다음 수부터 탐색
			sel[k] = arr[i]; // 수 선택
			combination(k + 1, i); // 다음 수 선택
		}
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 선택할 수 있는 경우의 수에 의해 결정된다. 최악의 경우, 모든 조합을 탐색해야 하므로 𝑂(𝑁^𝑀)의 시간 복잡도를 가진다고 볼 수 있다. 각 단계에서 수를 선택하는 연산이 상수 시간에 이루어진다는 점을 고려할 때, 주어진 문제 크기에 대해 충분히 빠르게 동작한다.

느낀점

이 문제를 통해 조합을 사용하여 수열을 생성하는 기본적인 방법을 실습할 수 있었다. 특히, 비내림차순 조건을 만족시키기 위한 조합 방식의 구현이 중요한 포인트였다. 이와 같은 방식은 다양한 조합 관련 문제에 적용될 수 있어 매우 유용하다.