491 비감소 부분 수열
문제 링크
문제 설명:
정수 배열 nums가 주어졌을 때, 모든 다른 비감소 부분 수열을 찾아 반환하세요. 비감소 부분 수열은 적어도 두 개의 요소를 가져야 합니다. 답변을 임의의 순서로 반환할 수 있습니다.
배열에는 중복 요소가 포함될 수 있습니다. 두 정수가 같은 경우에도 비감소 시퀀스의 특수한 경우로 간주할 수 있습니다.
예시 1:
<strong>입력:</strong>nums = [4,6,7,7]
<strong>출력:</strong>[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
예시 2:
<strong>입력:</strong>nums = [4,4,3,2,1]
<strong>출력:</strong>[[4,4]]
해결 코드: 해시 테이블 사용
class SubsequenceFinder {
private:
vector<vector<int>> outcomes;
vector<int> currentSequence;
void explore(vector<int>& nums, int beginIndex) {
if (currentSequence.size() > 1) {
outcomes.push_back(currentSequence);
}
bool used[201] = {false}; // 배열을 사용하여 중복 제거, 값 범위는 [-100, 100]
for (int i = beginIndex; i < nums.size(); i++) {
if ((!currentSequence.empty() && nums[i] < currentSequence.back())
|| used[nums[i] + 100]) {
continue;
}
used[nums[i] + 100] = true; // 이 레벨에서 사용된 요소 기록
currentSequence.push_back(nums[i]);
explore(nums, i + 1);
currentSequence.pop_back();
}
}
public:
vector<vector<int>> findNonDecreasingSubsequences(vector<int>& nums) {
outcomes.clear();
currentSequence.clear();
explore(nums, 0);
return outcomes;
}
};
해시 테이블 대신 set 사용
class SubsequenceFinder {
private:
vector<vector<int>> outcomes;
vector<int> currentSequence;
void explore(vector<int>& nums, int beginIndex) {
if (currentSequence.size() > 1) {
outcomes.push_back(currentSequence);
// 여기서 return하지 않음, 트리 노드 모두 수집
}
unordered_set<int> uniqueSet; // set을 사용하여 이 레벨의 요소 중복 제거
for (int i = beginIndex; i < nums.size(); i++) {
if ((!currentSequence.empty() && nums[i] < currentSequence.back())
|| uniqueSet.find(nums[i]) != uniqueSet.end()) {
continue;
}
uniqueSet.insert(nums[i]); // 이 레벨에서 사용된 요소 기록
currentSequence.push_back(nums[i]);
explore(nums, i + 1);
currentSequence.pop_back();
}
}
public:
vector<vector<int>> findNonDecreasingSubsequences(vector<int>& nums) {
outcomes.clear();
currentSequence.clear();
explore(nums, 0);
return outcomes;
}
};
46 모든 순열
문제 링크
문제 설명:
중복되지 않은 숫자 배열 nums가 주어졌을 때, 모든 가능한 순열을 반환하세요. 답변을 임의의 순서로 반환할 수 있습니다.
예시 1:
<strong>입력:</strong>nums = [1,2,3]
<strong>출력:</strong>[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
예시 2:
<strong>입력:</strong>nums = [0,1]
<strong>출력:</strong>[[0,1],[1,0]]
예시 3:
<strong>입력:</strong>nums = [1]
<strong>출력:</strong>[[1]]
해결 코드:
class PermutationGenerator {
public:
// 모든 고유한 순열 결과 저장
vector<vector<int>> allPermutations;
// 현재 구축 중인 순열 경로
vector<int> currentPermutation;
// 백트래킹 함수
void generatePermutations(vector<int> input, vector<bool> &usageStatus) {
// 기본 조건: 경로 길이와 입력 배열 길이가 같으면 완전한 순열이 완성됨
if (currentPermutation.size() == input.size()) {
allPermutations.push_back(currentPermutation); // 현재 순열을 결과 집합에 추가
return; // 현재 재귀 종료
}
// 모든 요소를 순회하여 순열 생성
for (int i = 0; i < input.size(); i++) {
// 현재 요소가 사용되지 않았다면
if (usageStatus[i] == false) {
usageStatus[i] = true; // 현재 요소를 사용됨으로 표시
currentPermutation.push_back(input[i]); // 현재 요소를 경로에 추가
// 다음 요소를 구축하기 위해 백트래킹 함수 재귀 호출
generatePermutations(input, usageStatus);
// 백트래킹: 선택을 취소하고 상태 복원
currentPermutation.pop_back(); // 경로에서 현재 요소 제거
usageStatus[i] = false; // 현재 요소를 사용되지 않음으로 표시
}
}
}
// 메인 함수, 입력을 받고 모든 고유한 순열 반환
vector<vector<int>> getAllPermutations(vector<int>& input) {
allPermutations.clear(); // 결과 집합 초기화
currentPermutation.clear(); // 현재 경로 초기화
vector<bool> usageStatus(input.size(), false); // 사용 상태 배열 초기화, 모두 미사용 상태
generatePermutations(input, usageStatus); // 백트래킹 함수 호출하여 순열 생성 시작
return allPermutations; // 생성된 모든 고유한 순열 반환
}
};
47 중복 순열
문제 링크
문제 설명:
중복 숫자를 포함할 수 있는 시퀀스 nums가 주어졌을 때, 모든 중복되지 않은 순열을 임의의 순서로 반환하세요.
예시 1:
<strong>입력:</strong>nums = [1,1,2]
<strong>출력:</strong>
[[1,1,2],
[1,2,1],
[2,1,1]]
예시 2:
<strong>입력:</strong>nums = [1,2,3]
<strong>출력:</strong>[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class UniquePermutationFinder {
private:
vector<vector<int>> allPermutations;
vector<int> currentPermutation;
void generatePermutations (vector<int>& nums, vector<bool>& used) {
// 완전한 순열을 찾은 경우
if (currentPermutation.size() == nums.size()) {
allPermutations.push_back(currentPermutation);
return;
}
for (int i = 0; i < nums.size(); i++) {
// used[i - 1] == true이면, 동일한 분기에서 nums[i - 1]가 사용됨
// used[i - 1] == false이면, 동일한 레벨에서 nums[i - 1]가 사용됨
// 동일한 레벨에서 nums[i - 1]가 사용된 경우 건너뛰기
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
used[i] = true;
currentPermutation.push_back(nums[i]);
generatePermutations(nums, used);
currentPermutation.pop_back();
used[i] = false;
}
}
}
public:
vector<vector<int>> getUniquePermutations(vector<int>& nums) {
allPermutations.clear();
currentPermutation.clear();
sort(nums.begin(), nums.end()); // 정렬
vector<bool> used(nums.size(), false);
generatePermutations(nums, used);
return allPermutations;
}
};
- 중복 제거 핵심 로직:
- 여기서 중복 제거 로직은 다음과 같습니다: ```
`if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; } `
- `i > 0`: 첫 번째 요소가 아님을 확인합니다.
- `nums[i] == nums[i - 1]`: 현재 요소와 이전 요소가 동일한지(중복인지) 확인합니다.
- `used[i - 1] == false`: 이전 동일한 요소가 사용되지 않은 경우에만 현재 요소를 고려합니다. 따라서 동일한 순열이 생성되지 않도록 이전 동일 요소를 사용할 때만 현재 요소를 사용합니다.
이것은 두 번째 요소가 이미 결정되었을 때(즉, 현재 요소가 true이고 이전 요소가 false인 경우)를 의미합니다. 이전 요소는 분명히 이미 고려되었을 것입니다. 왜냐하면 순회는 왼쪽에서 오른쪽으로 진행되기 때문입니다. 이때 `used[i - 1] == false`인 경우 continue를 하지 않으면 동일한 요소가 중복으로 고려될 수 있습니다.
1. **사용 상태 표시**:
- 특정 요소를 선택한 후 사용됨으로 표시: ```
used[i] = true; currentPermutation.push_back(nums[i]);
- 나머지 순열을 생성하기 위해 재귀 호출을 진행합니다.
- 재귀가 완료되면 상태를 되돌립니다: ```
`currentPermutation.pop_back(); used[i] = false; `
2. **메인 함수 `getUniquePermutations`**:
- `allPermutations`와 `currentPermutation`을 초기화하고, 요소 사용 상태를 추적하는 불 배열 `used`를 생성한 후 `generatePermutations` 함수를 호출합니다.