[アルゴリズム/Java]Baek JunとM(9)


質問リンク: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の場合は位置を変更)
  • .

    📃合成コード

    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());
    		}
    	}
    }