[Java] N과 M 2 [15650번]

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

• 예제 입력1

3 1

• 예제 출력1

1
2
3

• 예제 입력2

4 2

• 예제 출력2

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

• 예제 입력3

4 4

• 예제 출력3

1 2 3 4

---

• 문제 접근
  • N과 M 1의 문제에서 달라진 점은 앞의 수보다 뒤의 수가 작아야 함
  • 즉, 아래 같은 경우가 출력 되지 않음
    • 2 1
    • 3 1
    • 3 2
    • 4 1
    • 4 2
    • 4 3
• 문제 해결
  • 반복문의 시작값을 이전 i보다 1증가되어 시작
  • DFS 함수 매개 변수로 현재 시점이라는 now 변수를 전달
  • DFS 함수호출 시 현재 index를 1 증가, depth를 1증가하여 전달
    • 반복문의 i는 now부터 시작하여 numCount까지 반복

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

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));
    String[] input = br.readLine().split(" ");
    numCount = Integer.parseInt(input[0]); length = Integer.parseInt(input[1]);
    arr = new int[length];
    DFS(1, 0);
    System.out.println(sb);
}

private static void DFS(int now, int depth){
    if(depth == length){ // depth가 배열 길이랑 같아지면
        for(int num : arr)
            sb.append(num).append(" ");
        sb.append("\n");
        return;
    }

    for(int i = now; i <= numCount; i++){
        arr[depth] = i; // 현재 깊이의 방에 값 추가
        DFS(i + 1, depth + 1); // 현재 i의 +1을 해서 보내야 같은 값이 출력되지 않음
        /*
            ex) DFS(i, depth+1)
            => (1 1) (1 2) (1 3) ... (3 3) (3 4) (4 4)
        * */
    }
}

• Stream 풀이 [메모리 : 14512KB / 시간 : 136ms]

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(1, 0);
    System.out.println(sb);
}

private static void DFS(int now, int depth){
    if(depth == length){ // depth가 배열 길이랑 같아지면
        Arrays.stream(arr).forEach(num -> sb.append(num).append(" "));
        sb.append("\n");
        return;
    }

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

---

재귀를 스트림 API로 한다고 해서 무조건 성능 차이가 나는 것이 아니였음,,,

 

이전 코드와 달라진 점은 i값의 시작점이 점점 증가하여 재귀를 깊게 들어가지 않기 때문에 'N과 M 1'에 비해 재귀 호출이 현저히 적기 때문이라고 생각 됨

 

이전 'N과 M 1'에서 챗지피티의 말대로 스트림 API에서 추가적인 오브젝트 생성, 추가적인 메서드 호출 때문에 성능 저하로 연결된 것이 맞다라면?

재귀 호출이 적은 경우 전통적인 방식과 성능 차이가 크게 나지 않지만,

재귀 호출이 매우 많아질 경우 전통적인 방식과 성능 차이가 기하급수적으로 올라갈 것으로 예상 됨