[BOJ] 백준 15655 N과 M(6)

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

Approach

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

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

 

[BOJ] 15650 N과 M (2) 문제와 달리 임의의 Input Data가 주어진다.

또한, 정렬되지 않은 상태로 주어지는데, 

문제 조건에서 전체적으로 모든 Case를 출력시에는 사전순(오름차순)으로 출력해야 한다.

→ Input Data를 DFS 전에 정렬하면 된다.

 

---

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 idx, int depth) {
    if (depth == M) {
        for (int i = 0; i < M; ++i) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }
    for (int i = idx; i < N; ++i) {
        if (visited[i]) continue;
        visited[i] = true;
        ans[depth] = arr[i];
        DFS(i, depth + 1);
        visited[i] = false;
        ans[depth] = 0;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();
    mergeSort(0, N - 1);
    DFS(0, 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 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()));
        }
        
        // 문제에서 요구한 오름차순으로 출력하기 위해 정렬 해둔다.
        Collections.sort(list);
        
        // 순열 구성된 숫자들의 리스트
        List<Integer> answer = new ArrayList<>();
        
        // (중복없는) 조합리스트와 '0'번째 부터 뽑을지 안 뽑을지 재귀적으로 탐색
        combination(answer, 0);
    }

    
    private static void combination(List<Integer> answer, int idx) {
        // 문제에서 요구한 개수만큼 뽑았다면 출력
        if(answer.size() == M) {
            for(int i=0; i<answer.size(); i++) {
                System.out.print(answer.get(i) + " ");
            }
            System.out.println();
            return;
        }
        // 더 이상 뽑을 원소가 없다면 종료
        if(idx >= N) {
            return;
        }
        
        // idx번째 원소를 뽑는 경우
        answer.add(list.get(idx));
        combination(answer, idx + 1);
        
        // 위에서 넣은 원소를 다시 제거한다.
        // 넣었다 빼야 문제에서 요구한 오름차순 탐색이 가능한다.
        answer.remove(answer.size()-1);
        // idx번째 원소를 뽑지 않은 경우
        combination(answer, idx + 1);
    }
}

 

Reference

- 합병 정렬(Merge Sort) 

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

- [BOJ] 15650 N과 M (2)