Level 1: PCCP 기출문제 - 붕대 감기, 시간 경과에 따른 로직 계산

참고 문서

• Programmers: [PCCP 기출문제] 붕대 감기

이 문서의 내용

문제 풀이: 입출력 예시를 구현

이 문제에서 반복 처리하는 파라미터는 int[][] attacks입니다.

• 예시(1) : [[2, 10], [9, 15], [10, 5], [11, 5]]
• 예시(2) : [[1, 15], [5, 16], [8, 6]]

attacks는 [공격 시간, 피해량]을 갖는 튜플 자료형입니다. 입출력 예시처럼 각 시간에 따른 현재 체력 변화량을 계산하는 것이 핵심 로직입니다.

시간	현재 체력(변화량)	연속 성공	공격	비고
0	30	0	X	초기 상태
1	30(+0)	1	X	최대 체력 이상의 체력을 가질 수 없습니다.
2	20(-10)	0	O	몬스터의 공격으로 연속 성공이 초기화됩니다.
... (중략) ...
10	10(-5)	0	O	몬스터의 공격으로 연속 성공이 초기화됩니다.
11	5(-5)	0	O	몬스터의 마지막 공격입니다.

입출력 예시의 시간은 attacks의 마지막 Element가 가리키는 공격 시간에 의존합니다.

예시처럼 단순히 for (i = 0; i < 마지막 공격 시간; ++i) 루프하게 되면 시간 복잡도는 O(마지막 공격 시간)이 됩니다. 

• 예시 : [[10000000, 10]]

1개의 연산식을 처리하기 위해서 10000000회 루프하는 문제가 발생합니다!

문제 풀이: 시간 경과에 따른 로직 수행

이전 입출력 예시를 구현하면 시간 복잡도가 마지막 Element가 가리키는 공격 시간에 의존하는 문제가 있습니다.

각 연산식은 이전 연산을 기준으로 시간 경과에 따라서 처리 될 수 있습니다. 그렇게 되면 시간 복잡도는 O(배열의 크기)가 됩니다.

class Solution {
    public int solution(int[] bandage, int health, int[][] attacks) {
		int bandageTime = bandage[0];
		int bandageRate = bandage[1];
		int bandageBonus = bandage[2];
		int currhealth = health;
		int currTime = 0;
		
		for (int i = 0; i < attacks.length; ++i)
		{
			int attacksTime = attacks[i][0];
			int attacksValue = attacks[i][1];
			int deltaTime = (attacksTime - currTime);
			int gainHealth = (Math.max(0, deltaTime - 1) * bandageRate) + ((Math.max(0, deltaTime - 1) / bandageTime) * bandageBonus);
			currTime = attacksTime;
			currhealth = Math.min(health, currhealth + gainHealth);
			currhealth -= attacksValue;
			if (currhealth <= 0) return -1;
		}
		
		return currhealth;
	}
}

코드		비고
Line 6:7	currhealth	마지막 연산이 수행된 이후의 health입니다. 초기 값은 health입니다.
	currTime	마지막 연산이 수행된 이후의 time입니다. 초기 값은 0입니다.
Line 9	i < attacks.length	attacks의 Element만큼만 로직을 수행합니다. 시간 복잡도는 O(배열의 크기)입니다.
Line 13	deltaTime = (attacksTime - currTime)	마지막 연산이 수행된 이후의 time 변화량입니다.
Line 14	Math.max(0, deltaTime - 1)	지금 연산은 공격을 받은 순간입니다. 공격을 받기 직전까지의 time 변화량을 계산합니다.
	(Math.max(0, deltaTime - 1) * bandageRate)	공격을 받기 직전까지의 초당 회복량으로 회복된 수치를 계산합니다.
	(Math.max(0, deltaTime - 1) / bandageTime) * bandageBonus	공격을 받기 직전까지의 추가 회복량으로 회복된 수치를 계산합니다.
Line 16:17	Math.min(health, currhealth + gainHealth)	공격을 받기 직전까지의 회복된 수치를 더합니다. 체력은 초기 체력을 넘어서 회복 될 수 없습니다.
	currhealth -= attackValue	공격을 받은 직후의 체력입니다.

마지막 연산 시간과 공격 시간에 따른 시간 변화량 동안 체력 회복을 연산하고 데미지를 처리합니다.