[Silver II] N과 M (9) - 15663

문제 링크

성능 요약

메모리: 35564 KB, 시간: 312 ms

분류

백트래킹

제출 일자

2024년 5월 31 15:08:36

문제 설명

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

• N개의 자연수 중에서 M개를 고른 수열

입력

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

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

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

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

풀이 (백트래킹)

중복을 제거하기 위해 Set을 사용했다는 점을 제외하면 N과 M(8)과 크게 다르지 않게 해결할 수 있는 문제라고 생각한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class Main {
    //백트래킹
	static int N,M;
	static Set<String> set = new HashSet<>(); //중복 제거용
	static int[] array; //배열
	static int[] temp; //임시 배열
	static boolean[] visited; //방문 여부 확인
	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());
		array = new int[N];
		temp = new int[M];
		visited = new boolean[N];
		
		//배열 입력 받기
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			array[i]=Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(array); //오름차순 정렬
		
		repeat(0,0);//백트래킹 실행
		System.out.println(sb.toString());
	}
	public static void repeat(int num, int cnt) {
		if(cnt==M) { //만약 원하는 길이라면?
			StringBuilder temp_str = new StringBuilder();
			for(int i=0; i<M; i++) {
				temp_str.append(temp[i]).append(" ");
			}
			String str = temp_str.toString();
			if(!set.contains(str)) {//SET에 들어있지 않아야 함. (중복 제거)
				set.add(str);
				sb.append(str).append("\n");
			}
			return;
		}
		for(int i=0; i<N; i++) {
			if(!visited[i]) {//한번 들어갔던 배열 요소 참조 제거용
				visited[i]=true;
				temp[cnt]=array[i];
				repeat(i,cnt+1);
				visited[i]=false;
			}
		}
	}
}