[알고리즘] 백준 15651 N과 M (3) -백트랙킹- 자바 코틀린

 

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

15651번: N과 M (3)

 

 

 

백트랙킹 문제를 이어서 풀어봤습니다.

이번에는 각 자리수에 중복된 숫자가 와도 되는 오름차순 출력 조건입니다.

current로 재귀를 돌려야하고 isVisited 방문했는지 안했는지는 이번에는 필요없던게 포인트였습니다.

 

그리고 처음에 풀어서 제출했는데 시간초과가 났습니다.

그래서 출력부분을 StringBuilder로 바꿔서 해결했습니다. (Writer 까지는 필요없는것 같습니다.)

 

import java.util.Scanner;

public class Main {
    static boolean[] isVisited;
    static int[] num;
    static int n;
    static int m;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        isVisited = new boolean[m + 1];
        num = new int[m + 1];
        dfs(1);
        System.out.println(sb);
    }

    static void dfs(int current) {
        if (current > m) {
            for (int i = 1; i <= m; i++) {
                sb.append(num[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= n; i++) {
            num[current] = i;
            dfs(current + 1);
        }
    }
}

 

 

 

 

 

[2020-09-30]

[Java]

import java.util.Scanner;

public class Main {
    static boolean[] isVisited;
    static int[] num;
    static int n;
    static int m;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        isVisited = new boolean[m + 1];
        num = new int[m + 1];
        dfs(1);
        System.out.println(sb);
    }

    static void dfs(int current) {
        if (current > m) {
            for (int i = 1; i <= m; i++) {
                sb.append(num[i]).append(" ");
            }
            sb.append("\n");
            return;
        }
        for (int i = 1; i <= n; i++) {
            num[current] = i;
            dfs(current + 1);
        }
    }
}

 

 

[Kotlin]

import java.util.*

internal var isVisited: BooleanArray? = null
internal var num: IntArray? = null
internal var n: Int = 0
internal var m: Int = 0
internal var sb = StringBuilder()


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    n = sc.nextInt()
    m = sc.nextInt()
    isVisited = BooleanArray(m + 1)
    num = IntArray(m + 1)
    dfs(1)
    println(sb)
}

internal fun dfs(current: Int) {
    if (current > m) {
        for (i in 1..m) {
            sb.append(num!![i]).append(" ")
        }
        sb.append("\n")
        return
    }
    for (i in 1..n) {
        num!![current] = i
        dfs(current + 1)
    }
}

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다. !!