서로 다른 정수들의 컬렉션이 주어졌을 때, 가능한 모든 순열(permutation)을 찾아야 합니다. 이때 배열에 중복된 요소가 포함되어 있다면, 겉보기에 동일한 순열은 결과에서 제외해야 합니다. 예를 들어 배열이 [1,1,3]이라면, 결과는 [[1,1,3], [1,3,1], [3,1,1]]이 됩니다.
문제 해결 접근 방법
이 문제는 재귀(recursion)와 스왑(swap)을 활용한 백트래킹 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 자리에 올 수 있는 값을 하나씩 고정해 가며 순열을 만들되, 이미 처리한 값이 다시 등장하지 않도록 하는 것입니다. 구체적인 단계는 다음과 같습니다.
- 재귀적 접근 방식을 사용하며, 리스트와 인덱스(index)를 매개변수로 받습니다. 인덱스는 처음에 0으로 시작합니다.
- 인덱스가 리스트의 크기와 같아지면, 완성된 현재 리스트를 결과 배열(res)에 추가하고 함수를 종료합니다.
- i를 인덱스부터 리스트 길이 - 1까지 반복합니다.
- list[i]와 list[index]가 같으면서 i가 index와 다른 경우, 동일한 순열이 중복 생성되므로 해당 단계를 건너뜁니다.
- index 위치와 i 위치의 원소를 서로 교환(swap)합니다.
- permutation(list, index + 1)을 재귀 호출하여 다음 자리를 결정합니다.
- 처음에 permutation(list)를 호출한 뒤, 최종 결과 res를 반환합니다.
여기서 중요한 점은 탐색을 시작하기 전에 배열을 먼저 오름차순으로 정렬(sort)해 두면, 같은 값들이 인접하게 배치되므로 위의 중복 검사 조건(list[i] == list[index])만으로 간단히 중복 순열을 걸러낼 수 있다는 것입니다.
C++ 구현 예시
다음 구현을 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
void solve(vector <int> nums, int idx = 0){
if(idx == nums.size()){
res.push_back(nums);
return;
}
for(int i = idx; i <nums.size(); i++){
if(nums[i] == nums[idx] && i != idx)continue;
swap(nums[i], nums[idx]);
solve(nums, idx + 1);
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
res.clear();
sort(nums.begin(), nums.end());
solve(nums);
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,1,3};
print_vector(ob.permuteUnique(v));
}입력
[1,1,3]
출력
[[1,1,3],[1,3,1],[3,1,1]]
복잡도 분석
시간 복잡도는 최악의 경우 모든 원소가 서로 다를 때 O(n × n!)이며, 여기서 n은 배열의 크기입니다. 공간 복잡도는 재귀 호출 스택 깊이를 기준으로 O(n)입니다. 중복 원소가 많을수록 실제 생성되는 순열의 수는 n!보다 작아지므로, 위의 중복 검사 조건이 불필요한 탐색을 크게 줄여 줍니다.