풀이 소요시간 : 실패(시간초과)
자료의 수가 1,000,000 이기 때문에 O(nlogn) 복잡도 안쪽으로 해결해야 하는 문제다.
BFS 알고리즘을 활용한 탐색 문제라고 판단하고 문제를 풀었지만, 시간초과가 발생했다.
모든 경우의 수를 다 따져서 방어한 Round 를 저장해 정렬하여 최대 값을 뽑아내려했지만 정석적인 방식이 아니였다. 풀이 과정을 참고한 결과 우선순위 큐 자료구조를 활용하는 문제였다. 내가 우선순위 큐를 활용한 문제를 많이 안풀어봐서 전혀 떠올리지 못했다.
풀이 접근
내가 탐색으로 풀이를 결정하게 된 이유는, 이 문제가 BOJ 에서 풀어봤던 벽부수고 이동하기 문제와 유사하다는 생각을 했기 때문이다. 로직 자체가 틀린것 같지는 않지만 접근 방식이 잘못됬다.
무적권이 K 개 존재한다. 하지만 병사를 마주치는 그 순간에 무적권을 써야하는 상황인지 아닌지를 판단하는 것이 불가능하기 때문에 우선 가지고있는 병사로 막아내고, 막아낸 적들의 수를 우선순위 큐 에 저장시켜둔다.
더이상 다음 적군을 막아낼 병사가 남아있지 않다면 무적권을 사용한다. 무적권은 가장 많은 적군을 상대할 때 최고의 효율성을 발휘한다. 따라서 역대 최다수의 적군 과 현재 맞이하는 적군의 수 중 더 큰 적군에 무적권을 사용해야 최적의 결과가 발생한다. 무적권을 언제 사용할지 우선순위 큐를 사용해 나중에 결정할 수 있는 것이다.
위의 로직으로 코드를 짜면, 자력으로 막아낼 수 있는 Round + 무적권으로 막아내는 가장 많은 병사의 수 TOP K Round 의 결과 값이 발생한다. 해당 문제의 접근법을 기억해둬야겠다.
전체 코드
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int solution(int n, int k, vector<int> enemy) {
priority_queue<int> PQ;
int i = 0;
for(; i < enemy.size(); i++) {
//우선 방어 불가능할 때 까지 진행한다.
if(n - enemy[i] >= 0) {
PQ.push(enemy[i]);
// 막아낸 적군의 수를 저장해둔다. 오름차순으로 저장된다.
n -= enemy[i];
}
else {
//방어 불가능 & 무적권도 없으면 끝
if(k == 0) break;
else {
if(!PQ.empty() && PQ.top() > enemy[i]) {
//새로 들어오는 값이 더 작은경우, 역대 최다 적군에 무적권을 사용하고 작은 값은 우선순위 큐에 넣는다.
//새로 들어오는 값이 가장 큰 경우는 바로 통과한다. 무적권을 사용하고 우선순위 큐에 넣지 않는다.
n += PQ.top();
PQ.pop();
n -= enemy[i];
PQ.push(enemy[i]);
}
k--;
//항상 무적권은 가장 큰놈에게 사용된다.
}
}
}
return i;
}