[LeetCode] 60. Permutation Sequence

문제링크

permutation을 이용해서 배열의 원소들을 모두 이용하여 문자열을 만들었을 때, k번째 문자열을 반환하는 문제이다.

n개의 숫자를 사용해서 길이가 n인 permutation 생성

• seq[i]는 n개의 숫자 중에서 seq[0:i-1]에서 사용되지 않은 숫자들 중 어떠한 숫자도 될 수 있다
• 숫자가 사용되었는지 유무를 파악하기 위해 used array를 둔다

이를 코드로 정리하면 아래와 같다.

• str : 생성하고자 하는 permutation sequence
• count : 이때까지 생성된 permutation sequence의 개수. count가 k와 같으면 해당 permutation sequence를 반환한다.
• used[i] : i가 앞에서 사용되었는가의 여부를 나타냄.
• permutation(n, k, i) : str[i]의 원소를 채우는 재귀 함수.
• permutation(n, k, i)에서는 str[i]에 들어갈 수 있는 모든 숫자를 넣은 후, permutation(n, k, i+1)로 이동한다.

int count;
int array[10];
char answer[10];

int permutation(int n, int k, int start) {
	//길이가 n인 배열이 완성되었다면
    if(start==n)
    {
        count+=1;
        //해당 배열이 k번째 배열이라면
        if(k==count)
        {
            return 1;
        }
        return 0;
    }
    else
    {
    	//배열의 원소는 1~n까지이므로 1부터 시작
        for(int i=1;i<=n;i++)
        {
            if(!array[i])
            {
                array[i]=1;

                answer[start]=i+'0';
                int ret = permutation(n, k, start+1);
                if(ret) return 1;
                array[i]=0;
            }            
        }
    }
    return 0;
}

char * getPermutation(int n, int k){
    memset(array, 0, sizeof(array));
    memset(answer, '\0', (n + 1) * sizeof(char));
    count=0;
    
    permutation(n, k, 0);
    return answer;
}