[Silver II] N과 M (12) - 15666

문제 링크

성능 요약

메모리: 17224 KB, 시간: 272 ms

분류

백트래킹

제출 일자

2024년 7월 31일 20:10:36

문제 설명

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

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

출력

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

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

풀이 (재귀 + Set)

Set으로 중복을 제거한 후 재귀 함수를 이용해 해결한 문제다.

더 정확히는,

1. Set에 입력해야 하는 수를 넣어준다.
2. 오름차순으로 정렬해 배열에 넣어준다.
3. 재귀함수에서 for문으로 각각의 배열 값을 문자열에 추가해준다.
4. 재귀함수에서 아규먼트를 문자열, 출력할 길이, 반복문 시작 인덱스로 정한다.
5. 출력할 길이와 M의 값이 같아지면 출력하고 return한다.

로 해결했다!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.StringTokenizer;

public class Main {
	static int n,m;
	static int modifyN; //중복 제거한 배열 길이
	static ArrayList<Integer> list;
	static Set<Integer> set = new HashSet<Integer>(); //set으로 중복 걸러내기
	
	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());
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) { //set에 입력하기
			set.add(Integer.parseInt(st.nextToken()));
		}
		
		modifyN=set.size(); //수정된 길이
		
		list = new ArrayList<>(set); // set을 ArrayList로 변경
		Collections.sort(list, (o1,o2) -> o1 - o2); // 오름차순 정렬
		
		repeat("",0,0); //재귀 사용
		
	}
	public static void repeat(String str, int length,int idx) { //문자열, 길이, 반복문 시작 인덱스
		if(length==m) { //만족하는 길이가 됐다면 출력하기
			System.out.println(str);
			return;
		}
		
		for(int i=idx; i<modifyN; i++) {
			repeat(str+Integer.toString(list.get(i))+" ",length+1,i);
		}
	}
}