[Java] N과 M 11 [15665번]

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

• 예제 입력1

3 1
4 4 2

• 예제 출력1

2
4

• 예제 입력2

4 2
9 7 9 1

• 예제 출력2

1 1
1 7
1 9
7 1
7 7
7 9
9 1
9 7
9 9

• 예제 입력3

4 4
1 1 2 2

• 예제 출력3

1 1 1 1
1 1 1 2
1 1 2 1
1 1 2 2
1 2 1 1
1 2 1 2
1 2 2 1
1 2 2 2
2 1 1 1
2 1 1 2
2 1 2 1
2 1 2 2
2 2 1 1
2 2 1 2
2 2 2 1
2 2 2 2

---

• 문제 접근
  • 같은 수를 여러 번 골라도 되지만, 중복 수열은 출력해선 안 됨
• 문제 해결
  • i = 0 ~ N 까지 모든 경우의 수 출력

• 기존 풀이 [메모리 : 172780 KB / 시간 : 1348 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);

    System.out.println(sb);
}

private static void DFS(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);
        return;
    }

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

• Stream 사용 시 시간 초과

---

Set 없이 중복 체크  [메모리 : 34696  KB / 시간 : 412 ms]

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 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);
    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;
    }

    int lastUsed = -1;
    for (int i = 0; i < numCount; i++) {
        int current = numList.get(i);
        if (current != lastUsed) { // 현재 숫자가 마지막에 사용된 숫자와 같지 않다면
            arr[depth] = current; // 현재 dpeth번방에 현재 숫자를 넣음
            DFS(depth + 1);
            lastUsed = current; // 재귀 종료 후, 마지막 사용된 숫자에 현재 숫자를 저장
        }
    }
}