[코딩 인터뷰 완전 분석] 재귀와 동적 프로그래밍 / 중복없는 순열

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define size 10
/*
8.8 중복있는 순열
문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라.
나열된 순열은 서로 중복되면 안된다.
*/
void swap(char *s, char *t) {
	char temp;
	temp = *s;
	*s = *t;
	*t = temp;
}

void permutation(char *s, int l, int r) {
	if (l == r)
		printf("%s\n", s);
	else {
		for (int i = l; i <= r; i++) {
			swap((s + l), (s + i));
			permutation(s, l + 1, r);
			swap((s + l), (s + i));
		}
	}
}

int main() {
	char a[size];
	printf("문자열을 입력하세요 : ");
	scanf("%s", &a);
	int n = strlen(a);
	permutation(a, 0, n - 1);
}

[동작 과정]

1. i번째 요소(그림에서 표현한 빨간 문자)와 left 인덱스에 있는 요소의 위치를 바꿔준다. (아래 수식의 a1,a2,a3)

2. left 인덱스 다음에 있는 나머지 요소들의 순열을 구한다. (위의 수식의 P(a1a2),P(a1a3),P(a2a3))

3. 다음 순열에 영향을 주지 않도록 배열 요소들의 위치를 되돌려 놓는다.

4. 배열의 마지막 인덱스에 다다르면 해당 문자열을 출력한다.

 

[수행 시간]

permutation 함수가 배열의 길이(n)만큼 실행된다. 그 다음 함수에서는 n-1번, n-2번, ... 만큼 실행되므로 총 n! 번 호출된다. 말단 노드의 개수는 n!개이고, 각 루트에서 말단 노드까지의 거리는 n이므로, 전체 노드(함수 호출)의 개수는 n*n!을 넘지 못한다. 총 시간 복잡도는 O(n*n!)이다.