겹치지 않는 N자리 수를 오름차순으로 출력하기

이번에는 제목 그대로 겹치지 않는 N자리 수를 오름차순으로 차례로 출력해 보도록 하겠습니다.

이때 N을 3이라고 가정을 하겠습니다. 

3자리 수 또한 오름차순으로 되어 있어야 합니다. 즉, 012는 되는데 132는 안 되는 겁니다.

 

012, 013, 014, 015, 016, 017, 018, 019, 023, 024, ..., 089, 123, ...., 789

 

위와 같이 출력될 것입니다.

첫째 자리의 최댓값은 7이고 둘째 자리의 최댓값은 8이고 셋째 자리의 최댓값은 9입니다.

규칙이 하나 보이지 않습니까?

왠지 모르게 각 자리의 최댓값이 10 - N + index인 것 같습니다. 

그면 몇 자리가 들어오더라도 최댓값을 설정할 수 있게 되었습니다. 

쉼표는 마지막에만 없으면 될 것 같으니 첫째 자리가 최댓값이면 쉼표를 출력하면 안 되겠네요.

(789가 마지막 수이면서 첫째 자리가 7일 때의 수는 789밖에 없습니다. )

아래의 코드를 보시기에 앞서서 함수, while문, write, 재귀함수, 마지막으로 알고리즘이 이해되지 않은 분들은 아래의 링크들을 참고부탁드리겠습니다.

 

함수는 여기서...

https://hig0617.tistory.com/21

 

while문은 여기서...

https://hig0617.tistory.com/12

 

write는 여기서...

https://hig0617.tistory.com/47

 

재귀함수는 여기서...

https://hig0617.tistory.com/25

 

알고리즘은 여기서...

https://hig0617.tistory.com/51

 

모든 링크를 확인하시거나 위의 내용을 다 알고 계신 분들은 코드를 보도록 하겠습니다.

 

#include <unistd.h>

void    print(int *arr, int n)
{
    char    c;
    int        i;

    i = -1;
    while (++i < n)
    {
        c = arr[i] + 48;
        write(1, &c, 1);
    }
}

void    answer(int *arr, int index, int n)
{
    if (index != 0)
    {
        arr[index] = arr[index - 1] + 1;
    }
    while (arr[index] <= 10 - n + index)
    {
        if (index == n - 1)
        {
            print(arr, n);
            if (!(arr[0] == 10 - n))
                write(1, ", ", 2);
        }
        else if (index < n - 1)
        {
            answer(arr, index + 1, n);
        }
        arr[index]++;
    }
}

void    print_combn(int n)
{
    int    index;
    int    arr[10];

    index = -1;
    while (++index < n)
    {
        arr[index] = index;
    }
    answer(arr, 0, n);
}

int main(void)
{
    print_combn(9);
    return (0);
}

.print_combn에서 우선 초기화를 시켜주었습니다. 

앞에서 설명드렸다시피 각 자리의 최솟값은 각 자리의 인덱스 번호를 뜻합니다. 

따라서 while문을 사용해서 초기화를 시켜주었습니다. 

 

answer은 초기화한 값, 작성할 인덱스 번호, 몇 자리인지를 인자로 받습니다. 

첫째 자리를 제외하고 각 자리는 앞의 자리보다 1이 무조건 큽니다. 그래서 if문으로 초기화해 준 모습입니다. 

다음으로 while문을 사용하여 각 자리의 해당하는 값을 구합니다. 

만약 현재 작성한 위치가 끝자리라면 print함수를 사용하여 출력해 주고 쉼표를 찍습니다. 근데, 여기서 출력하는 부분이 마지막 부분이라면 쉼표를 출력하지 않습니다. 

끝자리가 아니라면 재귀를 다음자리로 돌게 했습니다. 

 

print는 배열을 출력해 주는 함수입니다. 

 

조금 어려운 알고리즘이었는데 고생하셨습니다. 이해가 되지 않으시면 손으로 진행과정을 작성해 보시면 도움이 되실 것이라고 생각이 듭니다. 화이팅!!