문제 설명
n개의 요소를 가진 배열 A와 값 c가 주어졌다고 가정해 보겠습니다. 우리 시스템에는 '미친 워드 프로세서'가 설치되어 있는데, 이 프로세서는 문자를 자유롭게 입력할 수 있지만 연속으로 c초 동안 아무것도 입력하지 않으면 지금까지 작성한 모든 글자가 화면에서 사라집니다. 배열의 각 요소 A[i]는 i번째 문자를 입력한 시각(초)을 의미합니다.
우리의 목표는 n개의 문자를 모두 입력한 후, 화면에 최종적으로 남아 있는 문자의 개수를 구하는 것입니다.
입력 예시
A = [1, 3, 8, 14, 19, 20], c = 5인 경우를 살펴보겠습니다. 이때 출력은 3이 됩니다.
- 8초 시점에는 화면에 3개의 문자가 표시되어 있습니다.
- 마지막 입력(8초) 이후 5초가 지난 13초에 모든 문자가 사라집니다.
- 14초와 19초에 두 개의 문자가 새로 입력됩니다.
- 마지막으로 20초에 한 개의 문자가 더 입력되어, 총 3개의 글자가 화면에 남게 됩니다.
해결 접근 방법
이 문제는 배열을 한 번만 순회하면 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재까지 유지되고 있는 문자 수를 저장하는 변수 s를 1로 초기화합니다(첫 번째 문자는 항상 화면에 남습니다).
- 배열을 순회하면서 인접한 두 입력 시각의 차이(A[i] − A[i−1])를 확인합니다.
- 차이가 c 이하라면 이전 문자들이 아직 삭제되지 않았으므로 s를 1 증가시킵니다.
- 차이가 c보다 크다면 이전 문자들이 모두 삭제된 것이므로 s를 1로 초기화합니다.
알고리즘 단계
s := 1
n := 배열 A의 크기
for i := 1 부터 i < n 까지 (i를 1씩 증가하며 반복):
if (A[i] - A[i - 1]) <= c, then:
s를 1 증가
Otherwise:
s := 1
return sC++ 구현
더 잘 이해하기 위해 다음 구현을 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, int c) {
int s = 1;
int n = A.size();
for (int i = 1; i < n; i++) {
if ((A[i] - A[i - 1]) <= c) {
s++;
} else {
s = 1;
}
}
return s;
}
int main() {
vector<int> A = { 1, 3, 8, 14, 19, 20 };
int c = 5;
cout << solve(A, c) << endl;
}입력
{ 1, 3, 8, 14, 19, 20 }, 5출력
3
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 되므로 입력 크기에 비례합니다.
- 공간 복잡도: O(1) — 추가적인 메모리 없이 상수 공간만 사용합니다.