ksh021144

ksh021144

Learn more, Do more.

[LeetCode] 46. Permutations

1 분 소요

LeetCode - 46. Permutations 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/permutations/

풀이

nums에 있는 수를 이용하여 만들 수 있는 순열을 구하는 문제이다. nums의 모든 원소는 고유하고 문제 조건에 의해 nums.length의 최대 길이가 6이므로 원소를 뽑은 위치를 나타내기 위한 체크 배열을 이용하고, 뽑을 위치는 인덱스 i에 해당하므로 idx 위치에 i를 저장하였다.

재귀의 기저 조건(N == idx)에 도달했을 때 임의의 정수 벡터 sub를 생성하고 sub[i] = nums[idxArr[i]]를 해주면 기저에 도달하기 이전까지 선택했던 인덱스 위치의 원소를 뽑을 수 있다.

핵심 코드는 아래의 부분이다.

  1. 아직 선택하지 않은 인덱스(!useChk[i])인지 확인하고 선택하지 않은 경우에만 수행한다.
  2. i 위치를 선택했다고 true로 표시한 후, 뽑은 인덱스를 순서대로 저장한다. (idxArr[idx] = i)
  3. 재귀 호출을 하며, 이때 다음의 인덱스가 저장될 위치는 idx + 1이므로 idx + 1을 매개변수로 전달한다.
  4. 재귀 호출이 끝나고 되돌아오면 i 위치를 선택하지 않았다고 표시한다. (useChk[i] = false)
for (int i = 0; i < N; ++i) {
    if (!useChk[i]) {
        useChk[i] = true;
        idxArr[idx] = i;
        perm(N, nums, result, idx + 1);
        useChk[i] = false;
    }
}

소스 코드

class Solution {
    bool useChk[6];
    int idxArr[6];
    void perm(const int N, const vector<int>& nums,
            vector<vector<int>>& result, int idx) {
        if (N == idx) {
            vector<int> sub(N);
            for (int i = 0; i < N; ++i) {
                sub[i] = nums[idxArr[i]];
            }
            result.push_back(move(sub));
            return;
        }
        for (int i = 0; i < N; ++i) {
            if (!useChk[i]) {
                useChk[i] = true;
                idxArr[idx] = i;
                perm(N, nums, result, idx + 1);
                useChk[i] = false;
            }
        }
    }

public:
    vector<vector<int>> permute(vector<int>& nums) {
        const int N = (int)nums.size();
        vector<vector<int>> result;
        fill(useChk, useChk + N, false);
        perm(N, nums, result, 0);
        return result;
    }
};

이 문제는 nums의 길이가 6이라 어느 방식으로 구현해도 큰 차이는 없을 것 같지만, swap을 사용하면 i를 0부터 시작하여 이미 사용하고 있는 위치를 몇 번씩 더 확인해야 할 필요으므로 인덱스를 일일이 검사하고 선택하는 것보다 빠를 것 같다. (마침 문제 조건에도 결과값 배열은 임의의 순서로 이루어져도 된다고 한다.) 만약 nums 배열이 오름차순으로 정렬되어 있고 순열을 순서대로(사전순으로) 생성해야 한다면 지금 작성한 코드가 좀 더 나을 것 같다.

참고