문제 소개
리그 오브 레전드(LOL)의 세계에 티모(Teemo)라는 영웅이 있다고 가정해 봅시다. 티모의 공격은 적인 애쉬(Ashe)에게 중독 상태를 일으킵니다. 여기서 티모가 애쉬를 공격한 시점들을 오름차순으로 정렬한 배열과, 한 번 공격할 때마다 중독이 지속되는 시간이 주어집니다. 우리가 구해야 하는 것은 애쉬가 중독 상태로 있게 되는 총 시간입니다.
단, 티모는 특정 시점의 시작 부분에서 공격하며, 공격하는 순간 애쉬는 즉시 중독 상태에 빠진다고 가정합니다.
예제로 이해하기
공격 시점 배열이 [1, 4]이고 중독 지속 시간이 2초라면, 정답은 4입니다. 그 이유는 다음과 같습니다.
- 시점 1: 티모가 애쉬를 공격하고, 애쉬는 즉시 중독 상태가 됩니다. 이 중독 효과는 2초간 지속되어 시점 2가 끝나는 순간까지 유지됩니다.
- 시점 4: 티모가 다시 공격하여 애쉬는 이번에도 2초간 중독 상태가 됩니다.
두 구간이 서로 겹치지 않으므로, 중독 상태의 총 지속 시간은 2 + 2 = 4초가 됩니다.
풀이 접근 방법
이 문제는 구간 병합(interval merging) 아이디어로 깔끔하게 해결할 수 있습니다. 핵심은 이전 공격의 중독 효과가 아직 남아 있는 동안 새로운 공격이 들어오면, 겹치는 부분을 중복해서 세지 않고 이어 주는 것입니다. 단계별로 살펴보겠습니다.
- 결괏값
ret = 0, 마지막 중독 종료 시점currEnd = -1로 초기화합니다. n은 공격 시점 배열t의 크기입니다.i를 0부터 n-1까지 반복하면서 다음을 수행합니다.- 현재 공격의 시작과 끝을 계산합니다:
start = t[i],end = t[i] + d - 1 currEnd < start라면 이전 중독 효과가 이미 끝난 것이므로 구간 전체를 더합니다:ret += end - start + 1, 그리고currEnd = end로 갱신합니다.- 그렇지 않다면(중독 효과가 아직 남아 있어 구간이 겹치는 경우) 새로 늘어나는 부분만 더합니다:
ret += end - currEnd, 그리고currEnd = end로 갱신합니다.
- 현재 공격의 시작과 끝을 계산합니다:
- 반복이 끝나면
ret을 반환합니다.
C++ 구현
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findPoisonedDuration(vector<int>& t, int d) {
int ret = 0;
int currEnd = -1;
int n = t.size();
for(int i = 0; i < n; i++){
int start = t[i];
int end = t[i] + d - 1;
if(currEnd < start){
ret += end - start + 1;
currEnd = end;
} else {
ret += end - currEnd;
currEnd = end;
}
}
return ret;
}
};
main(){
vector<int> v = {1,4};
Solution ob;
cout << (ob.findPoisonedDuration(v, 2));
}
실행 결과
입력:
[1, 4]
2
출력:
4
마무리
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 추가 메모리 사용은 O(1)로 매우 효율적입니다. 공격 시점이 오름차순으로 정렬되어 있다는 조건 덕분에 각 공격마다 이전 중독 구간의 끝점(currEnd)만 비교하면 됩니다. 구간이 겹치는지 여부를 판단해 누적 시간을 계산하는 이 패턴은 회의실 예약 병합, 로그 세션 길이 계산 등 다양한 구간 처리 문제에도 응용할 수 있으니 잘 익혀 두시기 바랍니다.