[JAVA] 백준 15651 N과 M (3)_백트래킹

 

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

15651번: N과 M (3)

 

 접근 : 

 

 - 최대 크기 N 과 뽑아야 하는 갯수 M 을 입력 받는다.

 

 - 1부터 N까지 중복해서 M 개를 뽑는다.

 

 - DFS(Depth-First Search)로 구현해서 결과를 출력한다.

 

 

 

 코드 구현 : 

 

 - 이너 클래스 사용

import java.io.*;

public class Main {

	static class Dfs {
		private StringBuilder result;
		private int n;
		private int m;
		private int[] selected;

		public Dfs(int n, int m) {
			this.n = n;
			this.m = m;
			this.result = new StringBuilder();
			selected = new int[m];
		}

		void doDfs(int depth) {
			if (depth == m) {
				for (int j = 0; j < m; j++) {
					result.append(selected[j]).append(" ");
				}
				result.append("\n");
				return;
			}

			for (int i = 1; i <= n; i++) {
				selected[depth] = i;
				this.doDfs(depth + 1);
			}
		}

		String getResult() {
			return result.toString();
		}
	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String[] inputs = br.readLine().split(" ");

		Dfs dfs = new Dfs(Integer.parseInt(inputs[0]), Integer.parseInt(inputs[1]));

		dfs.doDfs(0);

		System.out.println(dfs.getResult());
		br.close();
	}
}

 

 

 - 이너 클래스 사용 X

import java.io.*;
public class Main {
    private static int n;
    private static int m;
    private static int[] selected;
    private static StringBuilder sb;

    static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);
        selected = new int[m];
        br.close();
    }

    static void recFunc(int k){
        if(k == m + 1) {
            for (int i : selected) {
                sb.append(i).append(' ');
            }
            sb.append('\n');
            return;
        }
        
        for(int i = 1 ; i <= n ; i++){
            selected[k-1] = i;
            recFunc(k+1);
        }
    }

	public static void main(String[] args) throws IOException {
        sb = new StringBuilder();
        input();
        recFunc(1);
        System.out.println(sb);
	}
}

 

 

 - Stream 사용 ( 메모리 증가 및 속도가 많이 감소하므로 가능한 사용 X )

import java.io.*;
import java.util.Arrays;

public class Main {
    private static int n;
    private static int m;
    private static int[] selected;
    private static StringBuilder sb;

    static void input() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        n = Integer.parseInt(inputs[0]);
        m = Integer.parseInt(inputs[1]);
        selected = new int[m];
        br.close();
    }

    static void recFunc(int k){
        if(k == m + 1) {
            Arrays.stream(selected).forEach(i -> sb.append(i).append(' '));
            sb.append('\n');
            return;
        }
        
        for(int i = 1 ; i <= n ; i++){
            selected[k-1] = i;
            recFunc(k+1);
        }
    }

	public static void main(String[] args) throws IOException {
        sb = new StringBuilder();
        input();
        recFunc(1);
        System.out.println(sb);
	}
}

 

 

메모리 사용량 및 속도 비교 

 

1. 이너 클래스 사용

 

2. 이너 클래스 사용 X (속도가 조금 느린 결과가 나왔지만 여러번 반복 시행하면 이너클래스 사용한 것과 큰 차이 X)

 

3. Stream 사용