[11주차_수요일] 디펜스 게임

[yeongleej]

• 사이트 : 프로그래머스(PG)
• 문제: 디펜스 게임
• 번호: 142085
• 레벨: Level 2

### 🤔 시간복잡도 고려사항

### 💡 풀이 아이디어

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• O(N)이하로 풀기

💡 풀이 아이디어

• 적들의 수가 많은 순으로 무적권 사용하기

  • 우선순위 큐 이용

  • 이때, 적이 들어오는 순서는 유지해야함

    • 매 라운드 적을 우선순위 큐에 넣고, 무적권을 사용못할 경우(pq.size() > k) 제일 약한 병사 뽑아서 싸우기
    • 제일 약한 병사랑도 지면 해당 라운드 i 반환
      • i는 현재 라운드-1 값을 나타내고 있기에 바로 반환 가능

        
        if(k>=N) return N;                 // 다 무조건으로 이길 수 있을 경우 

    for(int i=0; i<N; i++){ pq.offer(enemy[i]); // 큐에 현재 라운드 추가 if(pq.size() > k){ // 큐의 크기가 k보다 크면, 무조건 사용 불가로 int weak = pq.poll(); // 제일 약한애랑 싸우기 if(n-weak < 0) return i; // i는 현재라운드-1 값을 나타내기에 현재 라운드에서 지면 i반환 n-=weak; // 싸우고 병사 수 줄기 } } return N;

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ enemy의 길이 ≤ 1,000,000 → 10^6이므로 O(N logN)이하 가능

💡 풀이 아이디어

• 무적권을 사용해야하는 순간을 결정하는 문제
• BFS로도 해결할 수 있는 것 같지만 시간초과..일듯 따라서 그리디한 방식으로 결정
• 더이상 진행할 수 없을 때, 현재까지 진행한 라운드들에서 적들의 수가 가장 많은 라운드에서 무적권을 사용
  • 우선 순위 큐를 이용하여 현재까지 진행한 라운드를 저장하며 병사의 수를 줄임
  • 만약 현재 병사의 수로 다음 라운드를 진행할 수 없을 경우 무적권 사용
  • 우선 순위 큐에서 최댓값을 꺼내 그 라운드에서 무적권을 사용 → 그만큼 병사의 수를 증가
  • 무적권을 사용할 수 없을 경우에 게임 종료

    for (; round < len; round++) {
    for (; round < len; round++) {
    // 라운드마다 우선순위 큐에 집어넣음
    pq.offer(enemy[round]);
    // 만약 해당 라운드의 몬스터를 무찌를 수 없을 경우
    if (n < enemy[round]) {
    // 무적권이 없다면 게임 종료
    if (0 == k)
        break;
    // 현재 우선순위 큐에 들어가 있는 값들 중
    // 최댓값을 꺼내 해당 라운드 무적권 사용
    n += pq.poll(); // 해당 라운드의 몬스터 수를 다시 더해줌
    k--; // 무적권 감소
    }
    n -= enemy[round]; // 해당 라운드의 몬스터 수 만큼 병사 감소
    }

[yeongleej]

🤔 시간복잡도 고려사항

• enemy 라운드 개수 <= 1,000,000

=> O(N)으로 생각해보기

💡 풀이 아이디어

• 우선순위큐를 사용해서 가장 체력 소모가 덜한 라운드에 싸우기 (단, 라운드 순서대로 진행해야 함)
• k가 라운드개수(enemy.length)보다 크거나 같으면 모든 라운드 진행 가능함
• pq : 병사를 사용할 후보 라운드들을 저장

• tmp : 무적권 사용 개수

  • 무적권 개수가 k보다 커지면 우선순위큐에서 체력소모가 가장 작은 라운드를 꺼내서 싸우기

    // 무적권 개수가 k보다 커지면 pq에서 가장 약한 라운드로 소모하기
    int tmp = 0;
    for(int i=0; i<enemy.length; i++) {
        pq.add(enemy[i]);
        tmp++;
        if(tmp > k) {
            int e = pq.poll();
            if(n - e < 0) {
                answer = i;
                break;
            }
            n -= e;
            tmp--;
        } 
    
    }

풀고 보니깐 수빈님이 푸신대로 무적권의 개수가 pq의 크기가 될 수 있다는 것을 꺠달았습니다~~ 👍

[KodaHye]

🤔 시간복잡도 고려사항

• 1 ≤ 처음 가지고 있는 병사 수 ≤ 1,000,000,000
• 1 ≤ 사용 가능한 무적권의 횟수 ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy길이 * log(enemy길이) 이내로 문제 풀이를 해야 됨

💡 풀이 아이디어

처음에 BFS로 했는데, 메모리 초과가 나네요!! (제가 잘못 구현했을 수도 있어요,,,)

• 무적권을 사용하는 시점을 골라야 됨 (최대로 진행할 수 있는 곳까지 갔을 때, 그 중에서 가장 큰 것들은 무적권을 사용하면 됨)
  • enemy 배열을 처음부터 선형 탐색을 함
  • n과 현재까지 처리한 enemy의 수(합계) 비교
  • n보다 enemy 의 수(합계)가 더 크다면 무적권 사용하기 (PriorityQueue에서 가장 큰 값 빼주기)

PriorityQueue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());

int sum = 0;

// 큐에 하나씩 적들을 담으면서, n보다 적들의 합이 더 커진다면
// 큐에서 가장 많은 적들을 꺼내서 무적권을 사용하기
for(int i = 0; i < enemy.length; i++) {
    sum += enemy[i];
    q.add(enemy[i]);

    if(n < sum && k > 0) {
        int diff = q.poll();
        sum -= diff;
        k -= 1;
    }

    if(n < sum) break;
    answer = i + 1;
}