TIL 07-09 붕대감기

문제 정보

• 문제 이름: 붕대 감기
• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/250137
• 알고리즘 분류: 시뮬레이션 (Simulation), 큐 (Queue)

풀이 과정

1 문제 분석 및 제약 조건 확인

이 문제는 시간의 흐름에 따라 체력(health)이 변화하는 과정을 그대로 시뮬레이션하면 풀리는 문제다.

• 매초마다 기본 회복량(heal_per_sec)만큼 체력이 회복된다.
• 단, 공격을 당하면 그 순간의 회복은 무효가 되고, 연속 회복 시간(seq)이 0으로 초기화된다.
• 공격받지 않고 total_time초 연속으로 버티면 보너스 회복(extra_bonus_heal)을 추가로 받는다.
• 체력은 최대 체력(max_hp)을 넘을 수 없다.
• 체력이 0 이하가 되면 즉시 -1을 반환하고 시뮬레이션을 종료한다.
• 모든 공격이 끝난 시점에 남아있는 체력을 반환한다.

핵심은 "몇 초가 지났는가"와 "연속으로 공격받지 않은 시간이 몇 초인가"를 동시에 추적해야 한다는 점이다. 초 단위로 순회하되, 현재 초가 공격 시점인지 아닌지를 분기 처리하는 것이 관건이다.

2 알고리즘 및 자료구조 선택

• 자료구조: attacks 리스트를 deque로 변환해 사용했다. 공격 이벤트를 시간 순서대로 하나씩 꺼내 써야 하는데, 매번 attacks[0]을 확인하고 pop(0)으로 제거하면 리스트 앞에서 원소를 지울 때 O(n) 비용이 발생한다. deque.popleft()를 쓰면 이 연산이 O(1)이라 초 단위 반복문 안에서 반복 호출해도 효율적이다.
• 알고리즘: 정렬이나 그래프 탐색 없이, 1초씩 증가시키며 상태를 갱신하는 완전 시뮬레이션 방식을 택했다. 문제에서 주어지는 attacks가 이미 시간순으로 정렬되어 있다는 전제하에, 다음 공격 시간과 현재 초를 비교하는 방식으로 구현했다.

3 절차적 구현 흐름

1. bandage 배열에서 total_time, heal_per_sec, extra_bonus_heal을 분리해서 변수로 저장한다.
2. attacks를 deque로 변환하고, 첫 번째 공격 정보(attack_time, damage)를 미리 꺼내둔다.
3. sec을 1씩 증가시키며 무한 루프를 돈다.
4. 현재 초가 공격 시간과 같다면:
   • 연속 회복 카운트(seq)를 0으로 초기화한다.
   • 체력에서 damage를 뺀다.
   • 체력이 0 이하면 -1을 반환한다.
   • 더 이상 공격이 없다면(deque가 비었다면) 현재 체력을 반환한다.
   • 다음 공격 정보를 꺼내온다.
5. 공격이 없는 초라면:
   • heal_per_sec만큼 체력을 회복하고 seq를 1 증가시킨다.
   • seq가 total_time에 도달하면 보너스 회복을 추가하고 seq를 0으로 초기화한다.
   • 체력이 max_hp를 넘으면 max_hp로 고정한다.
6. 공격 시간이 남아있는 한 3~5번 과정을 반복하며, 모든 공격이 처리되면 최종 체력을 반환한다.

이 흐름에서 가장 신경 쓴 부분은 공격당한 그 초에는 회복이 발생하지 않는다는 조건과, 보너스 회복 카운트는 공격을 받는 즉시 리셋된다는 조건을 if-else 분기로 명확히 나눈 것이다.

4 시간 복잡도

• sec은 마지막 공격 시간까지 1씩 증가하므로, 전체 반복 횟수는 최대 공격 시간(attacks의 마지막 원소의 시간)에 비례한다.
• 공격 처리(popleft())는 각 공격당 O(1)이며, 전체 공격 수를 m이라 하면 O(m)이다.
• 따라서 전체 시간 복잡도는 O(T) (T는 마지막 공격이 발생하는 시각)로 볼 수 있다.
• 공간 복잡도는 attacks를 deque로 변환하는 데 사용한 O(m) 수준이다.