[BOJ] 백준 15654 N과 M(5)

출처: https://www.acmicpc.net/problem/15654

Approach

- Input Data로 주어지는 원소는 중복되지 않음을 보장

- 오름차순을 출력해야 하므로, 순열 전에 Sort 처리

- 재귀 방식으로 중복 없는 순열 구현

 

▶ 합병 정렬(Merge Sort)

합병 정렬(Merge Sort)

▶ 순열과 조합 (백준 N과 M 시리즈)

순열과 조합 (백준 N과 M 시리즈)

 

---

C / C++

#include <stdio.h>
const int MAX_N = 8 + 2;
int N, M, ans[MAX_N], arr[MAX_N], trr[MAX_N];
bool visited[MAX_N];

void input()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &arr[i]);
    }
}

void mergeSort(int start, int end) {
    // 0. base condition
    if (start >= end) return;
    // 1. divide
    int mid = (start + end) / 2;
    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j])
            trr[k++] = arr[i++];
        else
            trr[k++] = arr[j++];
    }
    while (i <= mid) trr[k++] = arr[i++];
    while (j <= end) trr[k++] = arr[j++];
    // 4. copy
    for (i = start; i <= end; ++i) {
        arr[i] = trr[i];
    }
}

void DFS(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; ++i) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 0; i < N; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        ans[depth] = arr[i];
        DFS(depth + 1);
        visited[i] = false;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();
    mergeSort(0, N-1);
    DFS(0);
}

 

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
public class Main {
       static List<Integer> list;
       static boolean[] visited;
       static int N, M;
       public static void main(String[] args) {
              Scanner sc = new Scanner(System.in);
              N = Integer.parseInt(sc.next());
              M = Integer.parseInt(sc.next());
              list = new ArrayList<>();
              for (int i = 0; i < N; i++) {
                     list.add(Integer.parseInt(sc.next()));
              }
              // 중복순열을 체크하기 위함
              visited = new boolean[N];
              // 문제에서 요구한 오름차순으로 출력하기 위해 정렬 해둔다.
              Collections.sort(list);
              List<Integer> answer = new ArrayList<>();
              // 0번째 인덱스부터 선택하거나 안하거나
              permutation(answer);
       }
       private static void permutation(List<Integer> answer) {
              // 문제에서 요구한 개수만큼 뽑았다면 출력
              if (answer.size() == M) {
                     for (int i = 0; i < answer.size(); i++) {
                           System.out.print(answer.get(i) + " ");
                     }
                     System.out.println();
                     return;
              }
              for (int i = 0; i < N; i++) {
                     // 아직 뽑지 않은 원소라면
                     if (!visited[i]) {
                           answer.add(list.get(i));
                           visited[i] = true;
                           permutation(answer);
                           answer.remove(answer.size() - 1);
                           visited[i] = false;
                     }
              }
       }
}