[Leetcode] #495. Teemo Attacking

문제 :

문제

 

예시:

 

오름차순으로 정렬된 리스트 timeSeries가 주어지고, timeSeries[i]는 티모가 애쉬를 공격하는 당시의 시간이다. 또 다른 파라미터로 주어진 duration은 티모의 독 공격이 지속되는 시간이다. 예를들어, 티모가 1초에 애쉬를 공격했을때 duration이 3초라면, 애쉬는 1 2 3 초의 기간동안 독 공격을 받게 된다. 하지만, 독 공격의 duration이 끝나기 전에 티모가 새로운 공격을 하면, 독 공격의 duration은 초기화 된다.

 

처음 든 생각 :  사실 어떠한 자료구조를 이용해야겠다는 생각은 들지 않았다. 일단 이 문제는 배열의 요소들로 숫자 장난을 치는 문제이고, 자료구조나 알고리즘을 떠올리기 보단 단순히 수학 + 기본적인 코드정도만 알면 쉽게 풀고 넘어갈 수 있는 문제였다.

 

아래는 내가 제출해 통과한 코드이다.

class Solution:
    def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:

        time = 0

        for i in range(len(timeSeries) - 1):
            if timeSeries[i] + duration - 1 < timeSeries[i + 1]:
                time += duration
            else:
                time += timeSeries[i + 1] - timeSeries[i]

        return time + duration

 

• 먼저, 결괏값(최종 독에 공격받은 시간)을 담을 변수 time을 선언해 주고, 0으로 초기화 한다.
• for 반복문을 사용한다. 
  • 여기서 range(len(timeSeries) - 1))을 사용한 이유는 다음과 같다.
    - 우리가 이 문제에서 비교해야 할 대상은 딱 두개다. 공격을 가한 '현재 시간(timeSeries[i])' + 'duration'이 '다음에 공격할 시간(timeSeries[i + 1])' 보다 짧은지 긴지만 비교하면 된다.
    - 하지만, 생각해보면 마지막 공격은 어떠한 조건에도 제약받지 않고 duration만큼의 공격을 한다. 왜냐하면 다음에 비교할 대상이 없기 때문! 
    - 하지만 마지막 공격 이전의 공격은 마지막 공격 시간과 조건 비교를 해줘야 하기 때문에 len - 1을 하였다.
• 첫번째 조건문은 현재 시간에 공격을 하고, duration안에 새로운 공격을 하는지 안 하는지 확인하기 위한 조건문이다. 만약, 이 조건문이 True라면, 맨 처음 초기화한 time변수에 duration만큼의 공격을 한 것이므로 time += duration을 해 준다.
• 그렇지 않다면, duration을 더해주는 대신(duration동안 새로운 공격을 하면 이미 돌고있던 duration은 무의미해짐), 다음 시간에서 현재 시간을 뺀 시간만 더해준다. 
  - 예를들어, timeSeries = [1,2,3], duration = [5]라고 가정해보자. 1초에 공격을 가해 5초간 지속된다면, (1, 2, 3, 4, 5)초까지 지속이 될 것이다. 이땐 간단히 time에다가 방금 지난 5초의 시간을 더해주면 되지만, 이 case에선 다음 공격이 바로 다음 2초에 가해지므로, duration은 초기화 되지만, 1초에 공격을 가한 시간(1.00초 ~ 2.00초)까지의 시간에는 공격이 가해졌으므로 단순히 다음 값에서 현재 값을 뺀 값을 시간에 더해준다
• 마지막으로 위에서 언급 했듯, 마지막 공격은 어떠한 제약도 받지 않으므로, 하지만 우리의 for문은 len - 1, 즉, 마지막 요소는 검사 자체를 안 했으므로 마지막 return문에 duration까지 합해 리턴 해 준다.

 

아래는 내가 받은 런타임 report이다.