[Java] N과 M 3 [15651번]

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

• 예제 입력1

3 1

• 예제 출력1

1
2
3

• 예제 입력2

4 2

• 예제 출력2

1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

• 예제 입력3

3 3

• 예제 출력3

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

---

• 문제 접근
  • 숫자 개수 N과 길이 M을 입력 받고, 1 ~ N까지, 1 ~ N까지 반복이 됨
• 문제 해결
  • 예제 2번을 이중 반복문으로 생각하면 i = 1 ~ N까지, 그 다음 depth에서 다시 i = 1 ~ N까지 반복 됨

• 기존 풀이 [메모리 : 68524KB / 시간 : 484ms]

static StringBuilder sb = new StringBuilder();
static int numCount, length;
static int[] arr;

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    numCount = Integer.parseInt(st.nextToken()); length = Integer.parseInt(st.nextToken());
    arr = new int[length];
    DFS(0);
    System.out.println(sb);
}

private static void DFS(int depth){
    if(depth == length){
        for(int num : arr)
            sb.append(num).append(" ");
        sb.append("\n");
        return;
    }

    for(int i = 1; i <= numCount; i++){
        arr[depth] = i;
        DFS(depth + 1);
    }
}

• Stream 풀이 [메모리 : 155224KB / 664ms]

static StringBuilder sb = new StringBuilder();
static int numCount, length;
static int[] arr;

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int[] input = Arrays.stream((br.readLine().split(" "))).mapToInt(Integer::parseInt).toArray();
    numCount = input[0]; length = input[1];
    arr = new int[length];
    DFS(0);
    System.out.println(sb);
}

private static void DFS(int depth){
    if(depth == length){
        Arrays.stream(arr).forEach(num -> sb.append(num).append(" "));
        sb.append("\n");
        return;
    }

    IntStream.range(1, numCount + 1)
            .forEach(i -> {
                arr[depth] = i;
                DFS(depth + 1);
            });
}

---

역시나 'N과 M 2'에 비해서 재귀 호출이 많아지고 출력이 많아지니 성능이 심각해지려고 함