문제 개요
n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 아말(Amal)은 하프타임 없이 진행되는 90분짜리 경기를 시청하려고 합니다. 경기의 매 순간(1분 단위)은 재미있는 순간이거나 지루한 순간일 수 있으며, 만약 연속해서 15분 동안 지루한 구간이 이어진다면 아말은 즉시 TV를 꺼 버립니다.
배열 A에는 재미있는 순간이 발생한 시점(분)이 담겨 있습니다. 우리의 목표는 아말이 실제로 경기를 시청하는 총 시간이 몇 분인지 계산하는 것입니다.
예를 들어 입력이 A = [7, 20, 88]이라면 출력은 35가 됩니다. 7분과 20분 사이의 간격은 13분으로 15분을 넘지 않아 계속 시청하지만, 20분 이후에는 다음 재미있는 순간인 88분까지 68분의 긴 공백이 생깁니다. 따라서 아말은 마지막으로 재미있었던 20분에서 15분을 더한 35분에 TV를 끄게 됩니다.
풀이 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
Define an array a of size: 100. n := size of A for initialize i := 1, when i <= n, update (increase i by 1), do: a[i] := A[i - 1] if a[i] - a[i - 1] > 15, then: Come out from the loop return minimum of (a[i - 1] + 15) and 90
핵심 로직 설명
알고리즘의 핵심은 인접한 두 재미있는 순간 사이의 간격을 검사하는 것입니다. 현재 재미있는 순간과 바로 앞 재미있는 순간의 차이가 15분보다 크다면, 그 사이에 지루한 15분이 연속으로 발생했다는 의미이므로 반복문을 종료합니다. 이때 아말은 직전 재미있는 순간부터 15분을 더 시청한 뒤 TV를 끕니다.
반대로 모든 재미있는 순간 사이의 간격이 15분 이내라면 경기 끝까지 시청하게 되므로, 최종 결과는 (마지막으로 확인한 재미있는 순간 + 15)와 90 중 작은 값을 반환하는 방식으로 결정됩니다.
C++ 구현 예제
더 나은 이해를 위해 다음 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A){
int i, a[100];
int n = A.size();
for (i = 1; i <= n; i++){
a[i] = A[i - 1];
if (a[i] - a[i - 1] > 15)
break;
}
return min(a[i - 1] + 15, 90);
}
int main(){
vector<int> A = { 7, 20, 88 };
cout << solve(A) << endl;
}입력
{ 7, 20, 88 }출력
35
복잡도 분석
이 알고리즘은 배열 A를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 고정된 크기의 배열 하나만 사용하므로 추가 공간 복잡도는 O(1)입니다. 입력 크기와 무관하게 빠르게 동작하는 효율적인 해법입니다.