이 섹션에서 우리는 한 가지 문제를 볼 것입니다. 여기서 n개의 요소가 배열에 제공됩니다. 배열의 순열이 존재하는지 여부를 확인해야 합니다. 각 요소가 앞이나 뒤에 있는 요소의 수를 나타내도록 하는 것입니다.
배열 요소가 {2, 1, 3, 3}이라고 가정합니다. 적절한 순열은 {3, 1, 2, 3}과 같습니다. 여기서 처음 3은 그 다음에 3개의 요소가 있음을 나타내고 1은 이 앞에 하나의 요소만 있음을 나타냅니다. 2는 앞에 두 개의 요소가 있음을 나타내고 마지막 3은 앞에 세 개의 요소가 있음을 나타냅니다.
알고리즘
checkPermutation(arr, n)
begin define a hashmap to hold frequencies. The key and value are of integer type of the map. for each element e in arr, do increase map[e] by 1 done for i := 0 to n-1, do if map[i] is non-zero, then decrease map[i] by 1 else if map[n-i-1] is non-zero, then decrease map[n-i-1] by 1 else return false end if done return true end
예시
#include<iostream> #include<map> using namespace std; bool checkPermutation(int arr[], int n) { map<int, int> freq_map; for(int i = 0; i < n; i++){ //get the frequency of each number freq_map[arr[i]]++; } for(int i = 0; i < n; i++){ if(freq_map[i]){ //count number of elements before current element freq_map[i]--; } else if(freq_map[n-i-1]){ //count number of elements after current element freq_map[n-i-1]--; } else { return false; } } return true; } main() { int data[] = {3, 2, 3, 1}; int n = sizeof(data)/sizeof(data[0]); if(checkPermutation(data, n)){ cout << "Permutation is present"; } else { cout << "Permutation is not present"; } }
출력
Permutation is present