白駿15663 NとM(9)


1.問題リンク


https://www.acmicpc.net/problem/15663

2.解答

  • Inputには重複値が含まれており、それをソートするロジックが追加されています.
  • 問題の条件に従って並べ替えた後、before変数を使用して現在の再帰文が以前に選択した値を選択しないようにします.
  • その後、通常のシーケンスロジックが適用され、visitが重複値を回避するためにチェックされます
  • Inputは出力量を増やすのでStringBuilderを使用して時間を減らすことができます.
  • 3.コード

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    
    public class Main {
    
        static int N, M;
        static int[] nums;
        static int[] candidate;
        static boolean[] visit;
    
        static StringBuilder sb = new StringBuilder();
    
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] nm = br.readLine().split(" ");
            N = Integer.parseInt(nm[0]);
            M = Integer.parseInt(nm[1]);
    
            nums = new int[N];
            visit = new boolean[N];
            candidate = new int[M];
    
            String[] line = br.readLine().split(" ");
            for (int i = 0; i < N; i++) {
                nums[i] = Integer.parseInt(line[i]);
            }
    
            Arrays.sort(nums);
    
            permutation(0);
    
            System.out.print(sb);
        }
    
        static void permutation(int depth) {
            if (depth == M) {
                for (int i = 0; i < M; i++) {
                    sb.append(candidate[i]).append(" ");
                }
                sb.append("\n");
    
                return;
            }
            /**
             * nums가 정렬되어있기 때문에 가능한 일이다.
             * nums = {1, 1, 7, 9} 로 정렬되어있다고 가정해본다.
             * for문에서 현재(i) 선택된 값을 before에 저장 후, 다음 반복에서 접근하는 값(i + 1)과 비교한다.
             * 따라서 0번째 1이 선택되면 1번째 1은 넘어가게 된다.
             * before가 없다면 (1, 7) (1, 9)가 두 번씩 나오게 된다.
             */
            int before = -1;
            for (int i = 0; i < N; i++) {
                if (!visit[i] && before != nums[i]) {
                    visit[i] = true;
                    candidate[depth] = nums[i];
                    before = nums[i];
                    permutation(depth + 1);
                    visit[i] = false;
    
                }
            }
        }
    }

    4.採点結果



    5.感じ

  • HashSetのすべての配列を最初に保存し、現在のセットに同じ配列があるかどうかを比較します.
  • しかし、これには時間がかかりすぎ、before変数を使用して以前の繰り返しで使用された値を除外しました.
  • Outputが多い場合は、StringBuilder
  • を使用することを推奨します.