[Java] N과 M 7 [15656번]

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

• 예제 입력1

3 1
4 5 2

• 예제 출력1

2
4
5

• 예제 입력2

4 2
9 8 7 1

• 예제 출력2

1 1
1 7
1 8
1 9
7 1
7 7
7 8
7 9
8 1
8 7
8 8
8 9
9 1
9 7
9 8
9 9

• 예제 입력3

3 3
1231 1232 1233

• 예제 출력3

1231 1231 1231
1231 1231 1232
1231 1231 1233
1231 1232 1231
1231 1232 1232
1231 1232 1233
1231 1233 1231
1231 1233 1232
1231 1233 1233
1232 1231 1231
1232 1231 1232
1232 1231 1233
1232 1232 1231
1232 1232 1232
1232 1232 1233
1232 1233 1231
1232 1233 1232
1232 1233 1233
1233 1231 1231
1233 1231 1232
1233 1231 1233
1233 1232 1231
1233 1232 1232
1233 1232 1233
1233 1233 1231
1233 1233 1232
1233 1233 1233

---

• 문제 접근
  • 모든 경우의 수를 출력 (자기 자신 포함)
• 문제 해결
  • 출력 예제 2번을 기준으로 이중 반복문으로 생각하면 0 ~ N, 0 ~ N 모두 출력

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

static StringBuilder sb = new StringBuilder();
static int numCount, length;
static int[] arr;
static List<Integer> numList = new ArrayList<>();

public static void main(String[] args) throws IOException{
    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];

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < numCount; i++) numList.add(Integer.parseInt(st.nextToken()));
    Collections.sort(numList);

    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 = 0; i < numCount; i++){
        arr[depth] = numList.get(i);
        DFS( depth + 1);
    }
}

• Stream 풀이 [메모리 : 210684 KB / 시간 : 920ms]

static StringBuilder sb = new StringBuilder();
static int numCount, length;
static int[] arr;
static List<Integer> numList = new ArrayList<>();

public static void main(String[] args) throws IOException{
    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];

    input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    for (int i = 0; i < numCount; i++) numList.add(input[i]);
    Collections.sort(numList);

    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(0, numCount)
            .forEach(i -> {
                arr[depth] = numList.get(i);
                DFS(depth + 1);
            });
}