495. Teemo Attacking (해석 + 풀이)

 

 

의역: 우리팀의 (리그오브레전드)티모 챔피언이 적의 애쉬 챔피언을 공격했을 때 티모의 독 데미지는 정수 duration 초 만큼 지속되며 각 초마다 1초의 데미지를 받습니다.

만약 독 데미지의 0이 되기전에 다시 티모가 공격을 한다면 데미지를 받는 시간이 duration으로 초기화 됩니다. timeSeries[] 배열이 티모가 공격을 한 시간일 때 에쉬가 받게 되는 총 데미지를 반환하시오

의역: 1초에 티모의 공격을 받는다면 - 1초: 총 데미지 1, 2초: 총 데미지 2 끝

4초에 티모의 공격 - 4초: 총 데미지 3, 5초: 총 데미지 4 끝

의역: 1초에 티모의 공격을 받는다면 - 1초: 총 데미지 1

2초에 티모의 공격 - 2초: 총 데미지 2, 3초: 총 데미지 3 끝

 

풀이:

1. 비효율적이지만 실제 0~마지막 으로 공격이 들어오는 시간 까지의 경우를 반복문으로 체크 (time out)

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        // 시간 복잡도 O(nm) 공간 복잡도 O(1)
        int ans = 0;
        int demage = 0; // 앞으로 받게될 티모의 독 데미지 수치
        // 0초~timeSeries[] 마지막 값까지의 초를 일일이 카운트 해서 하는 방식
        for(int sec=0;sec<=timeSeries[timeSeries.length-1];sec++) {
            if (demage-- >0) ans++;
            for (int i = 0; i < timeSeries.length; i++) {
                if(sec==timeSeries[i])
                    demage = duration;
            }
        }
        ans+=demage;
        return ans;
    }
}

 

2. one pass 알고리즘 

+ One Pass 알고리즘: 정확히 한번 씩만 값을 읽어서 문제를 해결하는 것

위키백과: https://en.wikipedia.org/wiki/One-pass_algorithm

class Solution {
    public int findPoisonedDuration1(int[] timeSeries, int duration) {
        // 시간 복잡도 O(n) 공간 복잡도(1)
        int ans = 0;
        // 단순히 timeSeries의 배열 값만을 가지고 들어올 데미지 추정
        for(int i=0;i<timeSeries.length-1;i++){
            // 만약 duration(데미지가 지속되는 시간) 보다 들어오는 간격이 더 크다면
            if(timeSeries[i+1]-timeSeries[i]>duration)
                ans+=duration; // 온전히 duration의 데미지 추가
            // duration(데미지가 지속되는 시간) 보다 들어오는 간격이 더 작다면
            else // timeSeries[i]이때 받는 공격의 총 데미지는 시간의 차이만큼이 됨
                ans+=timeSeries[i+1] - timeSeries[i];
        }

        // 마지막에 들어온 공격은 온전히 duration 시간이 변하지 않기 때문에 그대로 추가
        return ans+duration;
    }
}

2-1 위에 코드에서 for 문을 foreach 문으로 바꾸어 속도를 더 개선한 코드

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int count = (timeSeries[0] == 0) ? 1 : 0;
        int stopTime = 0;
        for (int time : timeSeries) {
            if (stopTime >= time) {
                count -= stopTime - time + 1;
            }
            stopTime = time + duration - 1;
            count += duration;
        }
        return count;
    }
}

 

링크: https://leetcode.com/problems/teemo-attacking/description/