[BOJ/Java] 15663. N과 M (9)

[BOJ/Java] 15663. N과 M (9)

15663번: N과 M (9)

---

문제 해석

이 문제는 N개의 자연수 중에서 M개를 선택하여 만들 수 있는 모든 가능한 순열을 사전 순으로 출력하는 문제이다. 주어진 수들 중 중복된 값이 존재할 수 있으며, 출력되는 순열에서 중복되는 시퀀스는 제거되어야 한다.

풀이 과정

• 변수 선언 및 입력 처리: N은 주어진 자연수의 개수, M은 선택해야 하는 수의 개수이다. arr 배열에 입력받은 수를 저장하고 정렬한다.
• 중복 제거: 출력 시 중복되는 순열을 제거하기 위해 LinkedHashSet<String>을 사용한다. 이는 입력된 순서대로 데이터를 유지하면서 중복을 허용하지 않는 집합이다.
• 순열 생성: 재귀적 방법을 사용하여 가능한 모든 순열을 생성한다. 이미 사용한 요소는 비트마스킹을 통해 관리한다.
• 결과 출력: LinkedHashSet에 저장된 모든 순열을 반복하여 출력한다.

코드

package edu.ssafy.im.BOJ.Silver.S2.No15663;

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

public class Main {
	private static int N;  // 자연수의 개수
	private static int M;  // 선택할 자연수의 개수
	private static int[] arr;  // 입력받은 자연수를 저장할 배열
	private static int[] sel;  // 선택된 자연수를 저장할 배열
	private static Set<String> ans;  // 중복을 제거한 순열을 저장할 집합

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());  // 자연수의 개수 입력 받기
		M = Integer.parseInt(st.nextToken());  // 선택할 자연수의 개수 입력 받기
		
		arr = new int[N];
		sel = new int[M];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());  // 자연수 입력 받기
		}
		Arrays.sort(arr);  // 사전 순 출력을 위해 배열 정렬
		
		ans = new LinkedHashSet<>();  // 중복을 제거하기 위한 LinkedHashSet 초기화
		combination(0, 0);  // 순열 생성 시작
		
		for (String a : ans) {
			sb.append(a).append("\n");  // 저장된 순열 출력 준비
		}
		
		bw.write(sb.toString());  // 결과 출력
		bw.flush();
		bw.close();
	}

	private static void combination(int k, int v) {
		if (k == M) {  // M개의 자연수를 모두 선택했을 때
			StringBuilder sb = new StringBuilder();
			for (int s : sel) sb.append(s).append(" ");  // 선택된 순열을 문자열로 변환
			ans.add(sb.toString());  // 중복 제거를 위해 집합에 추가
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if ((v & (1 << i)) == 0) {  // 아직 선택되지 않은 자연수라면
				sel[k] = arr[i];  // 선택 배열에 저장
				combination(k + 1, v | 1 << i);  // 다음 숫자 선택
			}
		}
	}
}

시간 복잡도 분석

이 문제의 시간 복잡도는 𝑂(𝑁!)로 볼 수 있다. 각 단계에서 남은 요소들에 대한 순열을 생성하기 때문이다. 비트마스킹을 통해 이미 사용된 요소는 건너뛰므로 최악의 경우 모든 가능한 순열을 생성하게 된다.

느낀점

이번 문제는 순열 생성과 중복 제거를 함께 고려해야 하는 복잡한 문제이다. 이 문제를 통해 순열 생성 알고리즘과 자료구조를 활용한 중복 제거 방법에 대한 이해를 심화할 수 있었다. 또한, 중복된 요소가 있는 경우의 순열을 효과적으로 처리하는 방법을 배울 수 있었다.