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

문제 요약

게임 캐릭터는 붕대 감기 기술을 사용해 체력을 회복할 수 있다.

붕대 감기는 일정 시간 동안 유지되며, 매초 체력을 회복한다.

붕대 감기 정보는 다음과 같다.

bandage = [t, x, y]

각 값의 의미는 다음과 같다.

t = 붕대 감기 시전 시간
x = 1초당 회복량
y = t초 연속 성공 시 추가 회복량

캐릭터는 매초 x만큼 체력을 회복한다.

그리고 t초 연속으로 붕대 감기에 성공하면 추가로 y만큼 체력을 회복한다.

단, 캐릭터의 체력은 최대 체력 health를 넘을 수 없다.

몬스터에게 공격을 받는 순간에는 체력을 회복할 수 없다.

또한 공격을 받으면 붕대 감기가 취소되어 연속 성공 시간이 0으로 초기화된다.

몬스터의 공격을 받아 현재 체력이 0 이하가 되면 캐릭터는 죽는다.

모든 공격이 끝난 직후 캐릭터가 살아 있다면 남은 체력을 반환하고, 중간에 죽는다면 -1을 반환해야 한다.

접근 방법

매초마다 해야 할 일은 두 가지 경우로 나뉜다.

1. 현재 시간이 몬스터의 공격 시간인 경우
2. 현재 시간이 몬스터의 공격 시간이 아닌 경우

공격 시간이라면 캐릭터는 회복하지 못하고 피해를 받는다.

공격 시간이 아니라면 붕대 감기에 성공한 것이므로 체력을 회복한다.

공격 여부를 빠르게 확인하기 위해 attacks 배열을 딕셔너리로 바꿔준다.

attack_dict = {time: damage for time, damage in attacks}

필요한 변수

cast_time, heal_per_sec, bonus_heal = bandage

각 변수의 의미는 다음과 같다.

cast_time = t초 연속 성공 기준
heal_per_sec = 1초당 회복량
bonus_heal = 추가 회복량

현재 체력은 처음에 최대 체력과 같다.

current_health = health
max_health = health

연속으로 붕대 감기에 성공한 시간을 저장할 변수도 필요하다.

success_time = 0

마지막 공격 시간까지만 확인하면 된다.

last_attack_time = attacks[-1][0]

시뮬레이션 과정

시간은 1초부터 마지막 공격 시간까지 진행한다.

for time in range(1, last_attack_time + 1):

각 시간마다 공격이 있는지 확인한다.

1. 몬스터에게 공격받는 경우

현재 시간이 공격 시간이라면 체력을 회복하지 못한다.

대신 정해진 피해량만큼 체력이 감소한다.

current_health -= attack_dict[time]

공격을 받으면 붕대 감기가 취소되므로 연속 성공 시간은 0으로 초기화한다.

success_time = 0

만약 공격을 받은 뒤 체력이 0 이하가 되면 캐릭터가 죽은 것이다.

if current_health <= 0:
    return -1

2. 공격받지 않는 경우

현재 시간이 공격 시간이 아니라면 붕대 감기에 성공한 것이다.

먼저 연속 성공 시간을 1 증가시킨다.

success_time += 1

그리고 1초당 회복량만큼 체력을 회복한다.

current_health += heal_per_sec

만약 연속 성공 시간이 cast_time과 같아지면 추가 회복량도 더한다.

if success_time == cast_time:
    current_health += bonus_heal
    success_time = 0

붕대 감기가 끝나면 즉시 다시 사용하므로, 연속 성공 시간은 다시 0으로 초기화한다.

마지막으로 체력이 최대 체력을 넘지 않도록 처리한다.

current_health = min(current_health, max_health)

전체 코드

def solution(bandage, health, attacks):
    max_health = health
    cast_time, heal_per_sec, bonus_heal = bandage

    attack_dict = {time: damage for time, damage in attacks}

    current_health = health
    success_time = 0

    last_attack_time = attacks[-1][0]

    for time in range(1, last_attack_time + 1):
        if time in attack_dict:
            current_health -= attack_dict[time]
            success_time = 0

            if current_health <= 0:
                return -1

        else:
            success_time += 1
            current_health += heal_per_sec

            if success_time == cast_time:
                current_health += bonus_heal
                success_time = 0

            current_health = min(current_health, max_health)

    return current_health

예시로 이해하기

예를 들어 입력이 다음과 같다고 하자.

bandage = [5, 1, 5]
health = 30
attacks = [[2, 10], [9, 15], [10, 5], [11, 5]]

붕대 감기 정보는 다음과 같다.

5초 연속 성공하면 추가 회복
1초마다 체력 1 회복
5초 연속 성공 시 추가로 5 회복

처음 체력은 30이다.

1초

공격이 없으므로 체력을 회복한다.

체력 = 30
연속 성공 시간 = 1

체력은 이미 최대 체력이므로 더 회복해도 30을 넘을 수 없다.

2초

몬스터의 공격이 있다.

피해량 = 10

공격받는 순간에는 회복할 수 없다.

체력 = 30 - 10 = 20
연속 성공 시간 = 0

3초부터 7초

공격이 없으므로 붕대 감기에 성공한다.

5초 연속 성공하면 추가 회복이 발생한다.

3초: 체력 21, 연속 성공 1
4초: 체력 22, 연속 성공 2
5초: 체력 23, 연속 성공 3
6초: 체력 24, 연속 성공 4
7초: 체력 30, 연속 성공 0

7초에는 5초 연속 성공했으므로 기본 회복 1과 추가 회복 5가 적용된다.

단, 최대 체력이 30이므로 체력은 30까지만 회복된다.

9초

9초에는 몬스터의 공격이 있다.

체력 = 30 - 15 = 15
연속 성공 시간 = 0

10초

10초에도 몬스터의 공격이 있다.

체력 = 15 - 5 = 10
연속 성공 시간 = 0

공격받는 순간에는 회복할 수 없으므로 체력 회복은 일어나지 않는다.

11초

11초에도 몬스터의 공격이 있다.

체력 = 10 - 5 = 5
연속 성공 시간 = 0

모든 공격이 끝난 뒤 체력이 5이므로 결과는 다음과 같다.

return 5

시간 복잡도

마지막 공격 시간을 T라고 하자.

1초부터 마지막 공격 시간까지 한 번씩 확인하므로 시간 복잡도는 다음과 같다.

O(T)

공격 여부는 딕셔너리를 사용해 확인하므로 각 시간마다 O(1)에 처리할 수 있다.

공간 복잡도

공격 정보를 딕셔너리로 저장한다.

공격 횟수를 A라고 하면 공간 복잡도는 다음과 같다.

O(A)

정리

이 문제는 시간에 따라 체력 변화를 그대로 따라가면 되는 시뮬레이션 문제다.

핵심은 다음과 같다.

• 공격이 있는 시간에는 회복하지 않는다.
• 공격을 받으면 연속 성공 시간이 0으로 초기화된다.
• 공격이 없는 시간에는 체력을 회복하고 연속 성공 시간을 증가시킨다.
• 연속 성공 시간이 t초가 되면 추가 회복을 적용한다.
• 체력은 최대 체력을 넘을 수 없다.
• 공격 후 체력이 0 이하가 되면 즉시 -1을 반환한다.

즉, 이 문제는 공격 시간과 회복 시간을 구분하면서 체력과 연속 성공 시간을 관리하는 시뮬레이션 문제라고 볼 수 있다.