문제 설명
N개의 전구가 일렬로 나열되어 있으며, 1부터 N까지 번호가 붙어 있다고 가정해 봅시다. 처음에는 모든 전구가 꺼져 있습니다. 우리는 매일 정확히 하나의 전구를 켜며, N일이 지나면 모든 전구가 켜지게 됩니다.
길이가 N인 배열 bulbs가 주어질 때, bulbs[i] = x라면 (i+1)번째 날에 위치 x에 있는 전구를 켠다는 의미입니다. 또 다른 정수 K가 주어졌을 때, 켜진 두 전구 사이에 꺼진 전구가 정확히 K개 존재하는 가장 이른 날짜를 구해야 합니다. 만약 그러한 날이 없다면 -1을 반환합니다.
예시
입력이 bulbs = [1,3,2], K = 1이라면 출력은 2가 됩니다.
첫째 날: bulbs[0] = 1이므로 첫 번째 전구가 켜집니다 → [1, 0, 0]
둘째 날: bulbs[1] = 3이므로 세 번째 전구가 켜집니다 → [1, 0, 1]
셋째 날: bulbs[2] = 2이므로 두 번째 전구가 켜집니다 → [1, 1, 1]
둘째 날에는 켜진 두 전구(1번과 3번) 사이에 꺼진 전구가 하나 있었으므로 정답은 2입니다.
접근 방법
이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 먼저 각 전구가 몇 번째 날에 켜지는지를 저장하는
days배열을 만듭니다. 즉,days[bulbs[i] - 1] = i + 1로 설정합니다. - 왼쪽 경계
left와 오른쪽 경계right = left + k + 1사이에 있는 모든 전구가 양 끝의 전구보다 늦게 켜진다면, 이 구간은 조건을 만족하는 후보가 됩니다. - 중간에 양 끝보다 일찍 켜지는 전구가 발견되면 해당 위치부터 새로운 윈도우를 시작합니다.
알고리즘 단계
- n := bulbs의 크기로 설정합니다.
- i를 0부터 n-1까지 순회하며
days[bulbs[i] - 1] = i + 1을 저장합니다. - left := 0, right := k + 1, ret := INT_MAX로 초기화합니다.
- right < n인 동안 i를 증가시키며 반복합니다.
- 만약 days[i] < days[left] 또는 days[i] <= days[right]라면:
- i == right일 경우 ret := min(ret, max(days[left], days[right]))로 갱신합니다.
- left := i, right := i + k + 1로 윈도우를 이동합니다. - ret이 여전히 INT_MAX라면 -1을, 그렇지 않으면 ret을 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int kEmptySlots(vector<int>& bulbs, int k) {
int n = bulbs.size();
vector<int> days(n);
for (int i = 0; i < n; i++) {
days[bulbs[i] - 1] = i + 1;
}
int left = 0;
int right = k + 1;
int ret = INT_MAX;
for (int i = 0; right < n; i++) {
if (days[i] < days[left] || days[i] <= days[right]) {
if (i == right) {
ret = min(ret, max(days[left], days[right]));
}
left = i;
right = i + k + 1;
}
}
return ret == INT_MAX ? -1 : ret;
}
};
main(){
Solution ob;
vector<int> v = {1,3,2};
cout << (ob.kEmptySlots(v, 1));
}
입력
{1,3,2},
출력
2
복잡도 분석
시간 복잡도는 O(N)입니다. 각 인덱스가 최대 한 번씩만 방문되기 때문입니다. 공간 복잡도 역시 각 전구의 켜지는 날짜를 저장하는 days 배열 때문에 O(N)입니다.