Intuition

만들 수 있는 문자열의 경우의 수를 보는 문제인데, 중복이 안되는 것이다.

Approach & Solution

중복 여부를 알기위해 mask 배열을 사용했다.

int mask[9]; // 예를들어, 1이 사용된 경우에는 mask[0]=1
char res[10];
int cnt;

int p(int n, int k, int idx){
    int ret;

    if (idx==n){ // 하나의 sequence를 완성했을 때
        if (cnt==k) return 1; // k번째 sequence면 1 반환
        else{
            cnt++; // 그렇지 않으면 sequence counter++
            return 0;
        }
    }

    for (int i=0;i<n;i++){
        if (!mask[i]){ // 아직 쓰이지 않은 숫자일 경우
            res[idx]=i+1+'0'; // res배열은 char임에 유의
            mask[i]=1;
            ret=p(n,k,idx+1);
            if(ret) break; // 1이 반환되면 k번째 sequence이므로 재귀함수 탈출
            mask[i]=0; // ret으로 값이 반환됐다는 것은 하나의 sequence가 완성됐다는 뜻, 또 다른 경우의 수를 보기 위해 다시 0으로 되돌려주어야 함
        }
    }
    return ret;
}

char* getPermutation(int n, int k) {
    for (int i=0;i<9;i++){
        mask[i]=0;
        res[i]=0;
    }
    res[9]=0;
    cnt=1;
    p(n,k,0);
    return res;
}

Complexity

Time Compelxity

recursion의 과정을 tree구조로 표현했을 때,
첫번째 깊이에서 n
두번째에서 n-1개씩 n개
세번째 n-2개씩 n(n-1)개
.
.
.
즉, $n+n(n-1)+n(n-1)(n-2)+\cdots+n!=O(n!)$ 정도로 예상해 볼 수 있을 것 같다.

지적 및 질문 환영