문제 개요
이 문제에서는 n개의 요소로 이루어진 배열이 주어집니다. 배열의 각 요소는 경찰(P) 또는 도둑(T) 중 하나이며, 한 명의 경찰은 한 명의 도둑만 잡을 수 있습니다. 경찰이 자신으로부터 거리 k 이내에 있는 도둑을 잡을 수 있다고 할 때, 경찰 전체가 잡을 수 있는 도둑의 최대 마릿수를 구하는 것이 목표입니다.
예제로 이해하기
입력 −
array = {T, P, P, P, T, T, T}
K = 2출력 − 3
설명 − 각 경찰은 아래와 같이 한 명씩 도둑을 잡습니다.
인덱스 1의 P가 인덱스 0의 T를 잡음
인덱스 2의 P가 인덱스 4의 T를 잡음
인덱스 3의 P가 인덱스 5의 T를 잡음
경찰은 자신으로부터 거리 2 이내에 있는 도둑을 잡을 수 있으므로, 위와 같은 배정이 모두 허용됩니다.
접근 방법: 그리디 알고리즘
이 문제는 그리디(greedy) 알고리즘으로 해결할 수 있습니다. 크게 두 가지 방식을 생각해 볼 수 있습니다. 하나는 경찰에서 가장 가까운 도둑을 우선적으로 잡는 방식이고, 다른 하나는 가장 먼 도둑을 잡는 방식입니다. 하지만 두 방식 모두 경찰이 반드시 일정 거리 떨어진 도둑을 잡아야 하는 특정 경우에는 최적 해를 보장하지 못합니다.
따라서 다음과 같은 알고리즘이 가장 좋은 결과를 제공합니다.
첫 번째 경찰과 첫 번째 도둑의 인덱스부터 시작합니다. 만약 |index(P1) − index(T1)| ≤ k라면 해당 도둑은 잡힐 수 있으므로, 다음 경찰-도둑 쌍을 확인합니다. 그렇지 않다면 min(p, t), 즉 더 앞쪽에 위치한 포인터를 증가시켜 다음 경찰 또는 도둑의 인덱스를 검사합니다. 이 과정을 모든 경찰과 도둑을 확인할 때까지 반복한 뒤, 최종적으로 잡은 도둑의 수를 출력하면 됩니다.
이 알고리즘의 시간 복잡도는 O(n)이며, 경찰과 도둑의 위치를 저장하는 벡터 때문에 공간 복잡도 역시 O(n)입니다.
구현 예제
위에서 설명한 알고리즘을 C++로 구현한 프로그램입니다.
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int policeThief(char arr[], int n, int k){
int caught = 0;
vector<int> thieves;
vector<int> policemen;
for (int i = 0; i < n; i++) {
if (arr[i] == 'P')
policemen.push_back(i);
else if (arr[i] == 'T')
thieves.push_back(i);
}
int thief = 0, police = 0;
while (thief < thieves.size() && police < policemen.size()) {
if (abs(thieves[thief] - policemen[police]) <= k) {
caught++;
thief++;
police++;
}
else if (thieves[thief] < policemen[police])
thief++;
else
police++;
}
return caught;
}
int main(){
int k, n;
char arr2[] = {'P', 'T', 'T', 'P', 'P', 'T', 'T', 'T', 'T', 'P' };
k = 2;
n = sizeof(arr2) / sizeof(arr2[0]);
cout << "Maximum number of thieves that can be caught by police is :"<<policeThief(arr2, n, k);
return 0;
}
실행 결과
Maximum number of thieves that can be caught by police is :4