[Java] N과 M 8 [15657번]

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

• 예제 입력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 7
7 8
7 9
8 8
8 9
9 9

• 예제 입력3

4 4
1231 1232 1233 1234

• 예제 출력3

1231 1231 1231 1231
1231 1231 1231 1232
1231 1231 1231 1233
1231 1231 1231 1234
1231 1231 1232 1232
1231 1231 1232 1233
1231 1231 1232 1234
1231 1231 1233 1233
1231 1231 1233 1234
1231 1231 1234 1234
1231 1232 1232 1232
1231 1232 1232 1233
1231 1232 1232 1234
1231 1232 1233 1233
1231 1232 1233 1234
1231 1232 1234 1234
1231 1233 1233 1233
1231 1233 1233 1234
1231 1233 1234 1234
1231 1234 1234 1234
1232 1232 1232 1232
1232 1232 1232 1233
1232 1232 1232 1234
1232 1232 1233 1233
1232 1232 1233 1234
1232 1232 1234 1234
1232 1233 1233 1233
1232 1233 1233 1234
1232 1233 1234 1234
1232 1234 1234 1234
1233 1233 1233 1233
1233 1233 1233 1234
1233 1233 1234 1234
1233 1234 1234 1234
1234 1234 1234 1234

---

• 문제 접근
  • 앞의 인덱스는 출력하지 않고, 자기 자신은 출력
• 문제 해결
  • 2번 출력을 예시로 0 ~ N까지 출력 → 1 ~ N까지 출력 → 2 ~ N까지 출력
  • 현재 i를 넘겨주는 방식

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

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, 0);

    System.out.println(sb);
}

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

    for(int i = start; i < numCount; i++){
        arr[depth] = numList.get(i);
        DFS(i, depth + 1);
    }
}

• Stream 풀이 [메모리 : 20236 KB / 시간 : 220ms]

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, 0);

    System.out.println(sb);
}

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

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