1. 풀이

시도 1 - 완전탐색

완전 탐색시 시간복잡도가 O(eCk)인데, 이러면 최악의 경우 1000000C500000 이라 절대 불가..)

시도 2 - 큰 순서로 k개 찾고 -> 무적권 적용

정렬해서 가장 큰거 3개 찾고, 앞에서부터 벡터 순회하면서 무적권 적용 ?

• n=2, k=2 , enemy = [1,1,1,3,4] 이면 3,4 에 무적권 적용인데, 그전에 3라운드에서 죽어버림 -> 잘못된 가설임

옳은 풀이

이후에 어떤 방법 시도해볼지 못 떠올렸다. 답을 보고 풀었다.

우선순위 큐에 enemy의 수를 매 라운드 집어넣는다. 만약 우선순위 큐의 크기가 k보다 크면
-> 그때부턴 무적권으로 처리가 안되고, 내 병사 써서 막아야하므로
-> 우선순위 큐의 요소중 가장 작은 애를 누적한다. (사용한 병사를 누적하는 것임)
-> 그 과정에서 만약 누적 사용 병사의 수가 내가 가진 병사의 수 보다 커지면 반복 횟수를 반환한다.

사고 과정은..음...

문제 1. 나는 미래의 값과 비교해서 더 적군 적을때 내 병사로 상대하고, 적군 많을때 무적권 쓰고싶다. 그러나 앞에서부터 순회하면 미래의 값을 모른다. 어떻게할까?

-> 앞에서 부터 순회하며 일단 어떤 자료구조(무적권으로 커버할 적군의 수가 저장된다) 에든 넣어준다. 일단 무적권을 다 쓰는게 무조건 이득이니 자료구조의 크기 > 무적권 갯수가 되면 그 중 최소값을 찾아서 내 병사 쓰자.
-> 이렇게하면 가장 작은 적군 오는 라운드에서만 내 병사 쓸 수 있게된다.

문제 2. 최솟값을 어떻게 찾을까? 순회하면서 최솟값 찾으면 전체 시간복잡도는 O(e*k) 이고, 최악의 경우 연산량은 500000000000 = 5천억 이 되버린다. 어떡하지?

-> 우선순위 큐를 사용해서 최솟값 접근에 O(1)이 걸리도록 한다.

2. 코드

#include <string>
#include <vector>
#include <queue>
using namespace std;

int solution(int n, int k, vector<int> enemy)
{
    int sum = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < enemy.size(); i++) //O(N)
    {
        pq.push(enemy[i]); //O(logQ)
        if (pq.size() > k) //O(logk)
        {
            sum += pq.top();
            pq.pop(); //O(logk)
        }
        if (sum > n) return i;
    }
    return enemy.size();
}

시간복잡도는 어떻게 될까?

최악의 경우 for문 내부 코드가 모두 실행되므로, for 문 내부 시간복잡도는 O(logk)이고, 전체를 고려했을때 시간 enemy의 크기를 e라 두면, 시간 복잡도는 O(elogk)이다.

e가 최대 1000000, k가 최대 500000이므로, 최악의 경우 연산량은 1000000log500000 으로 안전하다.

3. 오답 노트

(1) 우선순위 큐 처음 사용해봄

우선순위 큐를 잘 몰랐어서, 우선순위 큐를 사용하면 된다는 것을 몰랐다

(2) 태도 : 가설 시도와 우디르급 태세 전환

여러 가설을 세우고 도전해보며 안되면 우디르급 태세 전환 했어야했는데 그러지 못했다. 어제 너무 바빴었다..ㅠ