N과 m (11)

[Silver II] N과 M (11) - 15665

문제 링크

성능 요약

• 메모리: 1116 KB
• 시간: 164 ms

분류

• 백트래킹

제출 일자

• 2024년 1월 6일 02:12:52

문제 설명

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

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

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

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

출력

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

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

TIL

• 내려가고, 올라올 때 이전 노드의 값을 초기화 잘 시켜주어야 한다.

BackTracing

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

내 접근

모든 부분을 잘 구현했지만, 내려갈 때 이전 노드의 값을 저장하는 변수를 다시 초기화시키는 로직을 생각 못했다. Level이 달라지면 이전 노드를 다시 방문해도 되기 때문.

내 코드

#include <stdio.h>

#define SIZE 8
void selectionSort(int arr[], int size);
void getPermutation(int list[], int N, int result[], int M, int depth, int* previousNode);
int main(){

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

    // selectionSort
    selectionSort(list, N);
    
    // getPermutation
    int previousNode = -1;
    int result[SIZE];
    getPermutation(list, N, result, M, 0, &previousNode);

    return 0;
}

// select result[depth]
void getPermutation(int list[], int N, int result[], int M, int depth, int* previousNode){
    if (depth == M){
        for (size_t i = 0; i < M; i++){
            printf("%d ", result[i]);
        }
        printf("\n");
        return;
    }

    // spreading
    for (size_t i = 0; i < N; i++){
        // pruning (내려가고, 올라올 때 언제 초기화하는지가 중요)
        if (*previousNode != list[i]){ 
            result[depth] = list[i];
            *previousNode = -1; // 내려가기 전에 깨끗하게 하기
            getPermutation(list, N, result, M, depth + 1, previousNode);
            *previousNode = list[i]; // 올라오면서 기록하기
        }
    }
}

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

시간 복잡도는
SelectionSort에서 O(N^2)
getCombination에서 O(N^M) 따라서 총 시간 복잡도는 O(N^M+N^2)

Feedback

재귀 함수에서 위와 같이 직접 하나하나 추적하는 것은 재귀적 사고에 도움이 되진 않지만, 예시를 들기 위해 보자. 같은 level에서만 직전 방문 값과 같으면 안되는 조건이 있으므로, 내려갈 때 초기화를 해주는 것. 비슷한 문제가 많아서 조건이 헷갈리기도 했는데, 이런 것도 훈련해봐야겠다.