[Conc & Sol] 주어진 조건을 반복 체크하여 경우의 수를 처리하는 구현 문제

▼ Why ? What ?

1일 1알고리즘 스터디에서 "붕대 감기"라는 문제를 풀었는데, 이 문제가 단순하진 않았어서 그런지 풀이 시간은 좀 오래 걸렸던 것 같다. 그래도 반례가 딱히 없고, 문제에서 제시한 것들을 그대로 구현해내면 문제없이 해결할 수 있는 문제인 것 같다. 첫 해결 코드도 문제에서 요구하는 답은 문제 없이 뽑아내지만, 단일 반복문으로도 처리할 수 있을 것 같아 코드를 리팩토링 해봤다. 매번 느끼지만 구현 문제는 문제에서 제시한 그대로 구현하려고 하기보단 내가 생각하기 편한 로직으로 바꿔 생각하는 것이 시간 단축에 많은 도움이 되는 것 같다.

---

▼ 알고리즘 문제 : "1번 / 붕대 감기"

 

[PCCP 기출문제] 1번 / 붕대 감기

프로그래머스

 

[ 나의 해결 코드 1 ]

• 공격을 받을 때마다 시간을 체크하도록 로직을 구성한 탓에 2중 반복문을 사용하게 된 것 같다.

class Solution {
    public int solution(int[] bandage, int health, int[][] attacks) {
        int curHealth = health;
        int demandTime = bandage[0];
        int healPerSec = bandage[1];
        int plusHeal = bandage[2];
        int healingTime = 0;
        boolean isDead = false;
        int currentTime = 0;
        
        for (int i = 0; i < attacks.length; ++i) {
            int damage = attacks[i][1]; // 다음 공격의 피해량
            int nextAttackTime = (i > 0 ? attacks[i][0] - attacks[i-1][0] : attacks[0][0]); // 다음 공격까지 힐할 수 있는 시간
            // 다음 공격을 받을 때까지 "붕대 감기" 시전
            for (int j = 1; j <= nextAttackTime; ++j) {
                if (j == nextAttackTime) { // 공격 당한 경우
                    healingTime = 0;
                    curHealth -= damage;
                    
                    if (curHealth <= 0) { // 피가 0이 된 경우
                        isDead = true;
                        break;
                    }
                    continue;
                }
                
                healingTime++; // 붕대 감기 시간 1초 증가
                curHealth += healPerSec; // 초당 회복
    
                if (healingTime == demandTime) { // 연속으로 붕대 감기 성공
                    healingTime = 0;
                    curHealth += plusHeal; // 추가 회복
                }
                
                if (curHealth > health) { // 최대 체력을 넘긴 경우
                    curHealth = health;
                }
            }
            
            if (isDead) { // 피가 0이 됐는지 체크
                curHealth = -1;
                break;
            }
        }
        
        return curHealth;
    }
}

 

[ 나의 해결 코드 2 ]

• 항상 구현 문제는 문제에서 제시한 로직대로 구현하게 되면, 시간복잡도 측면에서 가장 효율적인 코드를 뽑아내기는 힘든 것 같다.
  ➙ "시간"이라는 개념에 연연하지 않고 문제에 접근한다면, 단일 반복문으로 쉽게 문제를 해결할 수 있다.
  
  
• 리팩토링하다보니 이 문제를 해결할 때 "시간"으로 주어진 값을 "횟수"라고 생각하고 접근하면 더 헷가리는 부분 없이 해결할 수 있었을 것 같다.

class Solution {
    public int solution(int[] bandage, int health, int[][] attacks) {
        int maxHealth = health; // 최대 체력
        int demandTime = bandage[0]; // 시전 시간 -> 추가 회복을 하기 위해 필요한 연속 회복 횟수
        int healPerSec = bandage[1]; // 1초당 회복량
        int plusHeal = bandage[2]; // 붕대를 연속으로 감았을 때 추가 회복량
        int currentTime = 0; // 현재 시간
        
        for (int[] attack : attacks) {
            int healingTime = attack[0] - currentTime - 1; // 다음 공격까지 회복할 수 있는 시간 -> 횟수
            health = Math.min(maxHealth, health + (healPerSec * healingTime));
            if (healingTime / demandTime > 0) {
            	// healingTime/demandTime : 공격 전에 연속으로 붕대 감을 수 있는 횟수
            	health = Math.min(maxHealth, health + plusHeal * (healingTime / demandTime));
            }
            
            health -= attack[1]; // 이번 공격의 피해량만큼 체력 감소
            currentTime = attack[0]; // 현재 시간을 이번에 공격한 시간으로 갱신
            if (health <= 0) return -1; // 피가 0 이하가 되어 죽은 경우
        }
        
        return health;
    }
}