[프로그래머스] Java / Level 1 - 붕대감기 | PS일지

 

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

프로그래머스

 

---

 

어려운 점은 없었다. 

이번 문제는 입력 범위가 작아서 마지막 공격시간까지 1초씩 순회하며, 시간의 흐름에 따라 공격과 회복을 처리했다.

 

(이 문제는 아니지만 이런 유형의 문제가 만약에 마지막 공격 시간이 매우 크거나 매초 추가적인 반복문까지 수행하는 구조람녀 시간 초과가 날 수도 있다.)

 

 

구현하면서 한 가지 조심해야 할 점은

매번 시간이 지나서 체력을 매 초마다 증가시킬 때 health를 넘지 않아야 한다는 것이다.

public class 붕대감기 {
    public int solution(int[] bandage, int health, int[][] attacks) {
        int lastAttackIdx = attacks[attacks.length-1][0];
        int h = health;
        int healPoint = 0;
        int attackIdx = 0;
        for (int i =1; i <=lastAttackIdx;i++) {
            if (attacks[attackIdx][0] == i) {
                healPoint = 0;
                h -= attacks[attackIdx][1];
                attackIdx++;
                if (h <=0) return -1;
                continue;
            }
            healPoint++;
            h+= bandage[1];
            if (healPoint == bandage[0]) {
                healPoint = 0;
                h += bandage[2];
            }
            if (h>=health) h = health;
        }
        return h <=0 ? -1 : h;
    }
}

 

내 코드에서 개선해야 할 점은 어차피 공격이 '오름차순' 으로 정렬되어 나왔다. 그렇게 문제에 주어지지 않았더라도 시간의 흐름에 따른 공격 순서로 정렬해서 공격한 시간 별 체력 변화로 문제를 풀면 마지막 공격이라는 시간까지 순회하는게 아니라 공격 횟수만큼만 순회할 수 있다... 이런게 잘 안떠오르는 것 같다.

 

현재 문제에서는 입력 범위가 작아 두 방식 모두 통과할 수 있지만, 시간 값이 커질 가능성이 있다면 전체 시간을 순회하기보다 이벤트가 발생하는 시점을 기준으로 계산하는 방식이 더 효율적이다.

 

 

 

  개선 포인트 1. "정말 매 초를 봐야하나?"

시간 : 1 ~ 1,000,000,000 공격 횟수 : 100

 

이러면은 시간을 순회한다는 마인드 보다 이벤트를 순회하자는 마인드로 바뀌어야하는데에에엥..

 

  개선 포인트 2. 상태가 변화하는 순간을 캐치한다

체력이 변화하는 순간은 단 두개. 1. 공격 2 회복..

 

  개선 포인트 3. 연속된 동일한 작업은 묶을 수 있을까?

매 초 회복을 하면

+1
+1
+1
+1
+1

 

5번 더했구나~ 라고 생각하지만

1*5를 생각해보는.. 흠.. 이런 특정 이벤트 경계값 전까지 수식을 따져보아야 한다.

 

 

개선된 코드

public class 붕대감기 {
    public int solution(int[] bandage, int health, int[][] attacks) {
        int h = health;
        int previousAttackTime = 0;

        for (int[] attack : attacks) {
            int attackTime = attack[0];
            int damage = attack[1];

            int healTime = attackTime - previousAttackTime - 1;

            int healAmount =
                    healTime * bandage[1]
                    + (healTime / bandage[0]) * bandage[2];

            h = Math.min(health, h + healAmount);

            h -= damage;

            if (h <= 0) 
                return -1;

            previousAttackTime = attackTime;
        }

        return h;
    }
}