[프로그래머스/JAVA] 붕대 감기

목차 (OPEN)

• 🔗 문제 바로가기
• 📌 문제 요약
• 💡 아이디어
• 👩🏻‍💻 최종 코드
• 🕑 시간 복잡도

 

 

 

🔗 문제 바로가기

 

https://school.programmers.co.kr/learn/courses/30/lessons/250137

프로그래머스

 

---

📌 문제 요약

 

🕹️ 게임 규칙

• 캐릭터는 붕대 감기라는 기술을 써서 체력을 회복할 수 있다.
• 몬스터가 특정 시간에 내 캐릭터를 공격해서 체력을 깎는다.
• 캐릭터가 체력이 0 이하가 되면 죽는다.

 

🩹 붕대 감기란

• 시전 시간(t) 동안 매 초 x만큼 체력을 회복한다.
• t초 동안 한 번도 공격을 안 당하고 성공하면 y만큼 추가 회복한다.
• 회복 중 공격을 받으면 회복이 중단되고, 성공 시간이 0으로 초기화된다.
• 캐릭터의 체력은 최대 체력을 넘을 수 없다.

 

🎯 목표

• 공격을 다 맞고 나서도 캐릭터가 살아 있다면, 남은 체력을 return 한다.
• 도중에 캐릭터가 죽는다면 -1을 return 한다.

 

---

📥 입력

• bondage = [t, x, y]: 시전 시간, 초당 회복량, 추가 회복량을 담은 1차원 배열
• health: 캐릭터의 최대 체력
• attacks: [공격 시간, 피해량]이 담긴 2차원 배열

 

---

💡 아이디어

1️⃣ 입력으로 주어진 정보들 정리해두기

int max_health = health; // 최대 체력
int casting_time = bandage[0]; // 붕대 감기 시전 시간
int heal_per_sec = bandage[1]; // 초당 회복량
int bonus = bandage[2]; // 추가 회복량

int time = 0; // 현재 시간
int combo = 0; // 연속 회복 성공 시간
int attack_idx = 0; // 현재 공격 인덱스
int last_attack = attacks[attacks.length - 1][0]; // 마지막 공격 시간

 

 

2️⃣ 붕대 회복은 시간 단위로 진행하기

for (int i = 0; i <= last_attack; i++) {
    ...
}

 

• 전체 시간 흐름을 0초부터 마지막 공격 시간 (last_attack)까지 1초 단위로 반복하면서 체력 변화를 계산하였다.
• 실제 게임처럼 시간 순으로 매초 체력 회복과 공격 여부를 판단 할 예정이다.

 

3️⃣ 공격이 있는 시간에는 체력을 깎고, 회복 중단하기

if(attack_idx < attacks.length && attacks[attack_idx][0] == i){
    health -= attacks[attack_idx][1];            
    
    if(health <= 0){
        return -1;
    }
                
    combo = 0;
    attack_idx++;
}

 

• 만약 공격 시간과 현재 시간이 같다면
  • 체력을 피해량 만큼 깎고,
  • 즉시 회복을 중단하며,
  • 연속 회복 카운트(combo)를 0으로 초기화한다.
  • 이때, 만약 현재 체력이 0 이하가 되면 즉시 종료하고, -1을 return 한다.

 

4️⃣ 공격이 없는 시간에는 회복 계속하기

else{
    combo++;
    health += heal_per_sec;
    
    if(combo == casting_time){
        health += bonus;
        combo = 0;
    }            
    
    if(health > max_health){
        health = max_health;
    }
}

 

• 만약 공격 시간과 현재 시간이 다르다면
  • 초당 회복량(heal_per_sec) 만큼 체력을 회복하고,
  • 연속 회복 시간(combo)이 붕대 감기 시전 시간(casting_time)에 도달하면 bonus 만큼 추가 회복해준다.
  • 이때, 현재 체력이 최대 체력(max_health)을 넘지 않게 처리해준다.

 

---

👩🏻‍💻 최종 코드

 

class Solution {
    public int solution(int[] bandage, int health, int[][] attacks) {
        int max_health = health;
        int casting_time = bandage[0];
        int heal_per_sec = bandage[1];
        int bonus = bandage[2];
        
        int time = 0;
        int combo = 0;
        int attack_idx = 0;
        
        int last_attack = attacks[attacks.length - 1][0];
        
        for(int i = 0; i <= last_attack; i++){
            if(attack_idx < attacks.length && attacks[attack_idx][0] == i){
                health -= attacks[attack_idx][1];
                
                if(health <= 0){
                    return -1;
                }
                
                combo = 0;
                attack_idx++;
            }
            else{
                combo++;
                health += heal_per_sec;
                
                if(combo == casting_time){
                    health += bonus;
                    combo = 0;
                }
                
                if(health > max_health){
                    health = max_health;
                }
            }                                                                 
        }
        
        return health;
    }
}

 

---

🕑 시간 복잡도

내 코드를 간단히 구조화하면 아래와 같다.

for (int i = 0; i <= last_attack; i++) {
    if (공격이 있는 시점인가?) {
        공격 처리
    } else {
        회복 처리
    }
}

 

따라서 반복은 메인 루프에서만 존재하고, 루프 내의 연산들은 전부 O(1)이다.

 

👉🏻 즉, 시간 복잡도는 O(n)이다.

(이때, n은 마지막 공격 시간)