[アルゴリズム/Java]Baek JunとM(9)
21535 ワード
質問リンク:https://www.acmicpc.net/problem/15663
体感難易度:中
input():(静的)N,M,入力配列arr,アクセス配列初期化 makeAnswers():列を並べ替え、arrのN個の数の中からM個を選択すると、それを解答セット に保存する printAnswers():Comparator overriding で、答えセットの答えをスペースでString配列に分割し、arrsリストcollect→「辞書順にインクリメント」と列挙します.セットの使用:コレクションを使用して重複しない数列 を作成します. Comparator overlighting:TreeSetを使用してソートした結果、文字列昇順ではなく「11」<「6」の順にソートされます.(21%程度失敗)
→ダイレクトComparator overlightingメソッド を使用 Comparatorロジック:o 1配列(左)テキストとo 2配列(O)の要素を順番に比較し、要素が異なる場合はその要素のサイズ関係を比較します.
(戻り値<=0の場合は位置を変更し、戻り値>0の場合は位置を変更) .
📃合成コード
体感難易度:中
🤔に答える
→ダイレクトComparator overlightingメソッド
(戻り値<=0の場合は位置を変更し、戻り値>0の場合は位置を変更)
📃合成コード import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ15663_N과M9 {
static FastReader scan = new FastReader();
static int N, M;
static String[] arr;
static boolean[] visited;
static Set<String> answers = new HashSet<>();
public static void main(String[] args) {
input();
makeAnswers(0, 0, visited, "");
printAnswers();
}
private static void printAnswers() {
List<String[]> arrs = answers.stream()
.map(str -> str.split(" "))
.collect(Collectors.toList());
Collections.sort(arrs, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
for (int i = 0; i < M; i++) {
if (!o1[i].equals(o2[i])) {
if (Integer.valueOf(o1[i]).compareTo(Integer.valueOf(o2[i])) < 0) {
return -1;
}
return 1;
}
}
return 0;
}
});
for (String[] arr : arrs) {
System.out.println(String.join(" ", arr));
}
}
static void makeAnswers(int dept, int choice, boolean[] visited, String str) {
if (dept == M) {
answers.add(str);
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
String chosen = arr[i];
visited[i] = true;
makeAnswers(
dept + 1, choice + 1, visited, str.equals("") ? chosen : str + " " + chosen);
visited[i] = false;
}
}
}
static void input(){
N = scan.nextInt();
M = scan.nextInt();
arr = new String[N];
visited = new boolean[N];
Arrays.fill(visited, false);
for (int i = 0; i < N; i++) {
arr[i] = scan.next();
}
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
Reference
この問題について([アルゴリズム/Java]Baek JunとM(9)), 我々は、より多くの情報をここで見つけました
https://velog.io/@961210eee/알고리즘자바-백준-N과-M9
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ15663_N과M9 {
static FastReader scan = new FastReader();
static int N, M;
static String[] arr;
static boolean[] visited;
static Set<String> answers = new HashSet<>();
public static void main(String[] args) {
input();
makeAnswers(0, 0, visited, "");
printAnswers();
}
private static void printAnswers() {
List<String[]> arrs = answers.stream()
.map(str -> str.split(" "))
.collect(Collectors.toList());
Collections.sort(arrs, new Comparator<String[]>() {
@Override
public int compare(String[] o1, String[] o2) {
for (int i = 0; i < M; i++) {
if (!o1[i].equals(o2[i])) {
if (Integer.valueOf(o1[i]).compareTo(Integer.valueOf(o2[i])) < 0) {
return -1;
}
return 1;
}
}
return 0;
}
});
for (String[] arr : arrs) {
System.out.println(String.join(" ", arr));
}
}
static void makeAnswers(int dept, int choice, boolean[] visited, String str) {
if (dept == M) {
answers.add(str);
return;
}
for (int i = 0; i < N; i++) {
if (!visited[i]) {
String chosen = arr[i];
visited[i] = true;
makeAnswers(
dept + 1, choice + 1, visited, str.equals("") ? chosen : str + " " + chosen);
visited[i] = false;
}
}
}
static void input(){
N = scan.nextInt();
M = scan.nextInt();
arr = new String[N];
visited = new boolean[N];
Arrays.fill(visited, false);
for (int i = 0; i < N; i++) {
arr[i] = scan.next();
}
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
Reference
この問題について([アルゴリズム/Java]Baek JunとM(9)), 我々は、より多くの情報をここで見つけました https://velog.io/@961210eee/알고리즘자바-백준-N과-M9テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol