Codeforces Round #761 (Div. 2) - C. Paprika and Permutation

문제 링크 : Problem - C - Codeforces

Problem - C - Codeforces

 

그리디 + 바이너리 서칭 문제이다.

문제를 요약하면 인풋으로 받은 배열 A = [\(a_{1}\), ... , \(a_{n}\)] 에 대해서 \(a_{i}\) := \(a_{i}\) mod x (i ≠ x) 와 같은 작업을 수행함으로써 만들어진 배열이 1에서 n까지의 permutation 배열을 만들도록 하는 것이다.

permutation 배열은 예를 들어서 [1, 2, 3, 4], [1, 3, 2, 4], [3, 2, 1, 4], ... 등 다양하다.

이에 대한 성질을 생각해보면 1에서 n까지의 자연수가 각각 한 개씩 존재하도록 위와 같은 작업을 하면 된다.

즉, 문제에서 요구하는 것은 최소한의 작업으로 permutation 배열을 만들 수 있을 경우 해당 작업의 수를 출력하고 만들지 못할 경우 -1을 출력하도록 하는 문제이다.

 

문제 접근 방법

 

1. 인풋으로 받은 배열 A = [\(a_{1}\), ... , \(a_{n}\)] 을 오름차순 정렬을 시행한다.

 

2. 배열 A를 \(a_{1}\)부터 \(a_{n}\)까지 살피면서 두가지 케이스를 나눠서 작업을 수행한다.

이때 숫자가 겹쳤는지를 파악하기 위한 check 배열을 선언하였다. (bool check[100001])

그리고 작업을 수행하기 위한 숫자들을 보관하기 위한 벡터 v 을 선언하였다. (vector<int> v)

• \(a_{i}\) ≤ n 이면서 check[\(a_{i}\)] = false 인 경우 : 1에서 n까지의 숫자중 하나의 숫자가 나타났으므로 해당 숫자를 마킹해준다. (check[\(a_{i}\)] = true)
• 그렇지 않은 경우 : 벡터 v에다가 \(a_{i}\)값을 push 해준다.

 

3. 그 후에 1부터 n까지 for문을 돌려서 해당 숫자가 마킹될 경우와 마킹되지 않을 경우를 구분한다.

마캉된 경우 해당 숫자는 이미 permutation 배열의 하나의 수로 지정되었기 때문에 continue 하고 마킹되지 않은 경우 벡터 v에 저장된 가장 작은 숫자부터 큰 숫자까지 다음과 같은 작업을 수행하도록 한다.

 

그 전에 \(a_{i}\) := \(a_{i}\) mod x (i ≠ x) 에 대한 성질을 이해해보도록 해보자.

① \(a_{i}\) mod x 의 범위는 [1, x - 1] 임을 알 수 있다.

② i ≠ x 임을 고려할 때, \(a_{i}\) mod x 의 범위는 [1, \(a_{i}\) mod (\(a_{i}\) / 2 + 1)] 이다.

예를 들어 A = [1, 2, 3, 4, 18, 19, 5, 6, 7] 와 같은 배열이 있다고 가정해 보자.

18 mod 17 = 1, 18 mod 16 = 2, 18 mod 15 = 3, ..., 18 mod 10 = 8, 18 mod 9 = 0

19 mod 18 = 1, 19 mod 17 = 2, 19 mod 16 = 3, ..., 19 mod 10 = 9, 19 mod 9 = 1

18 일 경우 [1, 8] 의 범위를 갖는 것을 알 수 있고 19 일 경우 [1, 9] 의 범위를 갖는 것을 알 수 있다.

 

4. 3번 경우에서 마킹되지 않은 경우에 대해 두가지 조건을 고려할 수 있다.

이때 i는 permutation 숫자를 채워넣기 위한 용도로 1부터 n까지 1씩 증가하며 j는 벡터에 저장된 값을 나타내기 위한 용도로 0부터 1씩 증가한다.

• v[j] ≥ 2 * n + 1 일 경우 : continue 한다. 2 * n + 1 보다 크거나 같을 경우 mod 한 값의 범위는 항상 n 이하이기 때문이다.
• i ≤ v[j] mod (v[j] / 2 + 1) 일 경우 : j의 인덱스 값을 1 증가시켜 그 다음 벡터 값을 나타낸다.
• i > v[j] mod (v[j] / 2 + 1) 일 경우 : 이러한 경우는 permutation 배열을 만들 수 없는 경우이므로 -1 을 출력한 후 리턴한다.

 

5. 4번 작업까지 -1 을 출력하지 않고 모든 for - loop 을 돌았다면, 벡터 사이즈가 결국  최소한의 작업 횟수이므로 벡터 사이즈를 출력한 후 리턴한다.

 

 

Solution Code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int A[100001];
bool check[100001];

void test() {
	int n;
	vector<int> v;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		check[i] = false;
	}
	sort(A, A + (n + 1));
	for (int i = 1; i <= n; i++) {
		if (A[i] <= n && !check[A[i]]) {
			check[A[i]] = true;
		}
		else { 
			v.push_back(A[i]);
		}
	}

	for (int i = 1, j = 0; i <= n; i++) {
		if (check[i]) continue;
		if (v[j] >= 2 * n + 1) continue;
		int x = v[j] % (v[j] / 2 + 1);
		if (i <= x) j++;
		else {
			cout << -1 << endl;
			return;
		}
	}

	cout << v.size() << endl;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--) test();

	return 0;
}