[PROGRAMMERS] Level 2 디펜스 게임 (이진탐색, C++)

코딩테스트 연습 - 디펜스 게임 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

어제 올라온 따끈따끈한 신상 문제이다. 프로그래머스는 한 문제를 풀 때마다 점수를 주는데, 신상 문제를 풀면 점수를 굉장히 많이 획득할 수 있다. 쿄쿄

 

🎁 문제

준호는 요즘 디펜스 게임에 푹 빠져 있습니다. 디펜스 게임은 준호가 보유한 병사 n명으로 연속되는 적의 공격을 순서대로 막는 게임입니다. 디펜스 게임은 다음과 같은 규칙으로 진행됩니다.

• 준호는 처음에 병사 n명을 가지고 있습니다.
• 매 라운드마다 enemy[i]마리의 적이 등장합니다.
• 남은 병사 중 enemy[i]명 만큼 소모하여 enemy[i]마리의 적을 막을 수 있습니다.
  • 예를 들어 남은 병사가 7명이고, 적의 수가 2마리인 경우, 현재 라운드를 막으면 7 - 2 = 5명의 병사가 남습니다.
  • 남은 병사의 수보다 현재 라운드의 적의 수가 더 많으면 게임이 종료됩니다.
• 게임에는 무적권이라는 스킬이 있으며, 무적권을 사용하면 병사의 소모없이 한 라운드의 공격을 막을 수 있습니다.
• 무적권은 최대 k번 사용할 수 있습니다.

준호는 무적권을 적절한 시기에 사용하여 최대한 많은 라운드를 진행하고 싶습니다.

준호가 처음 가지고 있는 병사의 수 n, 사용 가능한 무적권의 횟수 k, 매 라운드마다 공격해오는 적의 수가 순서대로 담긴 정수 배열 enemy가 매개변수로 주어집니다. 준호가 몇 라운드까지 막을 수 있는지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• 1 ≤ n ≤ 1,000,000,000
• 1 ≤ k ≤ 500,000
• 1 ≤ enemy의 길이 ≤ 1,000,000
• 1 ≤ enemy[i] ≤ 1,000,000
• enemy[i]에는 i + 1 라운드에서 공격해오는 적의 수가 담겨있습니다.
• 모든 라운드를 막을 수 있는 경우에는 enemy[i]의 길이를 return 해주세요.

ex) input: n=7, k=3, enemy={4,2,4,5,3,3,1} // output: 5

📢 풀이

문제 지문만 읽으면 몇 가지 특징을 알 수 있다. 

첫 번째로는 탐색 문제라는 것이다. enemy 배열 안의 요소들을 파악하고 n과 비교하는 대표적인 탐색 문제다!

두 번째로는 enemy의 길이다. enemy의 길이는 최대 1,000,000으로 for문을 두 개라도 돌렸다가는 백퍼 시간초과가 날 것이다. 그렇다면 효율적으로 탐색할 수 있는 방법이 무엇이 있을까???

바로 이진탐색이다. 이진탐색을 많이 풀어봤다면 해당 문제를 읽어보고 대표적인 이진탐색 문제인 것을 파악할 수있다.

 

그렇다면 이제 예제를 손으로 먼저 풀어보자!

이진탐색은 low, high값을 지정하고 반 값 즉, mid 값으로 로직을 작성하는 탐색방법이다. enemy의 길이는 7이다.

즉, low=1, high=7이 될 것이다. mid 값은 (1+7)/2 = 4가 될 것이다. 그럼 enemy 배열의 0부터 4까지 쏙 빼와보면 {4,2,4,5,3}이 될 것이다. (여기서 무적권 k가 존재한다는 것을 잊으면 안된다!!)

무적권을 어떻게 써야 최대한 통과할 수 있을까?? 단순하게 높은 숫자부터 써주면 된다.

그럼 enemy 배열을 내림차순 정렬하면 {5,4,4,3,2}가 될 것이다. 그리고 k=3이므로 5,4,4를 막아낸다.

그럼 3과 2만 따져주면 문제를 해결할 수 있다. n은 7이고 총 적의 수는 5이므로 통과 가능하다. 그러므로 4단계까지는 진행할 수 있다. 이것을 low<=high가 될 때까지 반복해주면 이 문제는 쉽게 해결할 수 있다.

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

int solution(int n, int k, vector<int> enemy) {
    int answer = 0;
    if(k>=enemy.size()) return enemy.size();
    int low = 1, high = enemy.size();
    while (low <= high) {
        int mid = (low + high) / 2;
        vector<int> temp(enemy.begin(), enemy.begin() + mid);
        sort(temp.rbegin(), temp.rend());
        long long sum = 0;
        for (int i = k; i < temp.size(); i++) sum += temp[i];
        if (n - sum >= 0) {
            low = mid + 1;
            answer = mid;
        }
        else high = mid - 1;
    }
    return answer;
}

결과는 ....

정답을 맞췄을 때 바로 찍지못해서 점수가 출력이 안되었는데 해당 문제로 6점을 얻었다. 6점을 얻은 이유는 아무래도 현재 풀이가 많이 없어서 그런지 정답률이 굉장히 낮다. 그리고 이진탐색을 사용해서 시간을 상당히 줄였다. 아무래도 이 문제를 풀지 못했다면 이진탐색에 익숙하지 않아서 그런것이다.. 익숙해지면 밥먹듯 풀 수 있을 것이다. (저는 2시간 걸림)

 

📢 결론

하루에 백준 3문제, 프로그래머스 2~3문제 정도를 같이 풀고 있다. 요즘 기업들이 프로그래머스를 활용하거나 이와 유사한 형태로 코딩테스트를 제출해서 프로그래머스를 시작하게 되었다. 또, SQL 문제를 풀 수 있다는 점도 굉장한 장점이다.

백준은 문제 수가 많다보니 알고리즘, 난이도 별로 연습해 볼 수 있다. 내가 생각할 때는 프로그래머스 문제 수는 절대 백준을 따라 잡지 못한다.. 초보자라면 백준의 알고리즘 탭에 들어가서 하나씩 풀어보는 것을 더 추천한다.

 

오늘의 결론은 코테를 준비할 때 가장 좋은 방식은 프로그래머스, 백준 다 푸는 것이다 ^_^