N과 m (5)

[Silver III] N과 M (5) - 15654

문제 링크

성능 요약

메모리: 1116 KB, 시간: 36 ms

분류

백트래킹

제출 일자

2024년 1월 1일 19:44:37

문제 설명

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

TIL

• 가지치기와 return문을 이용한 소멸
• selectionSort

BackTracing

1. 확장
2. 가지치기
3. 끝까지 간뒤에 다시 올라오기 (이때 원상태로 복원시키면서)

Feedback

내 접근

N과 M의 이전 문제와 동일 다만, sort를 한번 해주어야 했는데, N=8이 최대 입력이여서 굳이 O(nlogn)의 시간복잡도를 가진 mergeSort, quickSort보다는 그냥 구현하기 쉬운 selectionSort를 복습할겸 직접 구현했다. O(n^2)이여도 시간초과는 발생하지 않을 것이기 때문.

내 코드

#include <stdio.h>
#include <stdbool.h>
#define SIZE 9
void selectionSort(int list[], int size);
void makeCombination(int arr[], bool isVisted[], int n, int list[], int M, int depth);

int main()
{

    // input
    int N, M;
    scanf("%d %d", &N, &M);
    int list[SIZE];
    for (size_t i = 0; i < N; i++)
        scanf("%d", &list[i]);

    // selectionSort
    selectionSort(list, N);

    int arr[SIZE] = {0};
    bool isVisted[SIZE] = {0};

    // getCombination
    makeCombination(arr, isVisted, N, list, M, 0);

    return 0;
}

void selectionSort(int list[], int size)
{
    for (size_t i = 0; i < size - 1; i++)
    {
        int minIndex = i;
        for (size_t j = i + 1; j < size; j++)
        {
            if (list[j] < list[minIndex])
                minIndex = j;
        }
        int temp = list[minIndex];
        list[minIndex] = list[i];
        list[i] = temp;
    }
}

// arr[depth]를 채우는 함수
void makeCombination(int arr[], bool isVisted[], int n, int list[], int M, int depth)
{
    if (depth == M)
    {
        for (size_t i = 0; i < M; i++)
            printf("%d ", arr[i]);
        printf("\n");
        return;
    }
    // 확장
    for (size_t i = 0; i < n; i++)
    {
        // 가지치기
        
        if (!isVisted[i])
        {
            // 방문
            arr[depth] = list[i];
            isVisted[i] = true;

            // 재귀
            makeCombination(arr, isVisted, n, list, M, depth + 1);
            // backTracking
            isVisted[i] = false;
        }
    }
}