15664. N과 M (10) (S2)
시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
1 초 | 512 MB | 16953 | 13400 | 11110 | 79.664 % |
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- N개의 자연수 중에서 M개를 고른 수열
- 고른 수열은 비내림차순이어야 한다.
- 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
summary
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
- N개의 자연수 중에서 M개를 고른 수열
- 중복된 결과값은 제외
- 오름차순
- 사전순
strategy
DFS (모든 경우의 수를 구하기)
- 각 자리마다 동일 숫자는 한번만 사용해야 하기 때문에 하나씩만 저장 (num)
- 각 숫자마다 사용 가능횟수를 기록 (count)
- 오름차순을 위해 이전 수를 기억 (start)
note
- 1 ≤ M ≤ N ≤ 8
- 10,000보다 작거나 같은 자연수
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[] count = new int[10001];
static List<Integer> num = new ArrayList<>();
static int[] result;
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());
result = new int[M];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
int current = Integer.parseInt(st.nextToken());
if(count[current] == 0) num.add(current);
count[current]++;
}
Collections.sort(num);
comb(0, 0);
System.out.println(sb.toString());
}
public static void comb(int cnt, int start) {
if(cnt == M) {
for(int current : result) {
sb.append(current).append(" ");
}
sb.append("\n");
return;
}
for(int n = start; n < num.size(); n++) {
if(count[num.get(n)] == 0) continue;
count[num.get(n)]--;
result[cnt] = num.get(n);
comb(cnt + 1, n);
count[num.get(n)]++;
}
}
}
문제 | 결과 | 메모리 | 시간 | 언어코드 | 길이 |
15664 | 맞았습니다!! | 14372 KB | 104 ms | Java 11 / 수정 | 1443 B |
memo
- 결과를 LinkedHashSet 에 저장하는 방법도 있다.
'문제 풀이 > 백준' 카테고리의 다른 글
[JAVA 26] 15666. N과 M (12) (0) | 2024.09.11 |
---|---|
[JAVA 25] 15665. N과 M (11) (0) | 2024.09.11 |
[JAVA 24] 15657. N과 M (9) (0) | 2024.09.11 |
[JAVA 24] 15657. N과 M (8) (0) | 2024.09.11 |
[JAVA 23] 15656. N과 M (7) (0) | 2024.09.11 |