[Java] N과 M 10 [15664번]

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

• 예제 입력1

3 1
4 4 2

• 예제 출력1

2
4

• 예제 입력2

4 2
9 7 9 1

• 예제 출력2

1 7
1 9
7 9
9 9

• 예제 입력3

4 4
1 1 2 2

• 예제 출력3

1 1 2 2

---

• 문제 접근
  • 이전 인덱스와 자기 자신을 포함하지 않음
• 문제 해결
  • 재귀 호출 시 현재 인덱스 + 1
  • ‘N과 M 9’와 동일하게 Set으로 중복 체크 필요

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

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

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];
    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){
        StringBuilder tmp = new StringBuilder();
        for(int num : arr) tmp.append(num).append(" ");
        tmp.append("\n");
        if(numSet.add(tmp.toString())) sb.append(tmp.toString());
        return;
    }

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

 

• Stream 풀이 [메모리 : 14604 KB / 시간 : 140ms]

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

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];
    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){
        StringBuilder tmp = new StringBuilder();
        Arrays.stream(arr).forEach(num -> tmp.append(num).append(" "));
        tmp.append("\n");
        if(numSet.add(tmp.toString())) sb.append(tmp);
        return;
    }

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