Baekjun No. 15649, N and M (1) (with.Java)

This article explores Baekjoon Problem 15649, N and M (1) (with Java).

I will learn by solving coding test problems, reflecting on previous problems, and exploring different solution methods.

Let’s first look at the problem.

Problem

Given natural numbers N and M, write a program that finds all sequences of length M that satisfy the following conditions.

A sequence of M numbers selected without repetition from 1 to N.

Input

The first line contains natural numbers N and M. (1 ≤ M ≤ N ≤ 8)

Output

Print one sequence per line that satisfies the conditions.

Duplicate sequences should not be printed multiple times, and each sequence should be separated by a space.

The sequences should be printed in increasing lexicographical order.

Problem Solution

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;

class Main{
    public static int[] arr;
    public static boolean[] visit;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s_arr = br.readLine().split(" ");
        br.close();
        int N = Integer.valueOf(s_arr[0]);
        int M = Integer.valueOf(s_arr[1]);

        arr = new int[M];
        visit = new boolean[N];

        dfs(N, M, 0);

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public static void dfs(int N, int M, int depth){
        if(depth == M){
            for(int i : arr){
                sb.append(i).append(" ");
            }
            sb.append("\n");
            return;
        }

        for(int i = 0; i < N; i++){
            if(!visit[i]){
                visit[i] = true;
                arr[depth] = i + 1;
                dfs(N, M, depth + 1);
                visit[i] = false;
            }
        }
    }
}

Solution Explanation

It uses BufferedReader and BufferedWriter to handle input and output.

First, it reads the input and stores it in N and M.

The arr array stores the selected numbers, and the visit array checks whether the selected numbers have been used.

A StringBuilder stores the results.

The dfs function finds all cases using a depth-first search.

If the current depth is equal to M, the selected numbers are stored in a StringBuilder in the output format and returned.

Otherwise, it iterates through the numbers from 1 to N, selecting an unused number and moving on to the next depth.

Once the selection is complete, the number is set back to unused.

Once this process is complete, the results stored in the StringBuilder are printed using a BufferedWriter and the program terminates.

This method efficiently generates and outputs all cases.