n개의 전구가 있는 방이 있다고 가정해 보겠습니다. 전구에는 1부터 n까지 번호가 붙어 있으며, 왼쪽에서 오른쪽으로 일렬로 배치되어 있습니다. 처음에는 모든 전구가 꺼져 있는 상태입니다. 순간 k(단, k는 0부터 n-1 사이의 값)마다 light[k] 번째 전구를 하나씩 켭니다. 어떤 전구는 자기 자신이 켜져 있고, 그 왼쪽에 있는 모든 전구들 역시 켜져 있을 때에만 파란색으로 바뀝니다. 우리가 구해야 하는 것은 '켜져 있는 모든 전구가 파란색'이 되는 순간의 개수입니다.
예를 들어 다음 그림과 같은 경우를 살펴보겠습니다 −
켜진 전구가 모두 파란색이 되는 순간은 총 3번이며, 각각 1, 2, 4번째 순간입니다. 따라서 출력값은 3이 됩니다.
문제 해결 접근 방법
이 문제는 맵(map)과 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다. 특정 시점에 켜진 모든 전구가 파란색이 되려면, 1번부터 해당 번호까지의 전구들이 정확히 앞선 순간들에 걸쳐 순서 없이 골고루 켜져 있어야 한다는 점입니다. 이 조건을 확인하기 위해 다음 단계를 따릅니다 −
결괏값 ret := 0으로 초기화하고, 집합(set) x와 맵 m을 정의한 뒤, 배열의 크기를 n에 저장합니다
최소 힙(min-heap) 기반의 우선순위 큐 pq를 정의합니다
i를 0부터 n-1까지 반복합니다
m[light[i]] := i 로 설정하여 '전구 번호 → 켜진 순간' 정보를 저장하고, i를 pq에 삽입합니다
i를 1부터 n까지 반복합니다
m[i], 즉 전구 i가 켜진 순간을 집합 x에 삽입합니다
pq가 비어 있지 않고 pq의 최상위 원소가 집합 x에 속해 있는 동안,
pq에서 해당 원소를 삭제(pop)합니다
pq가 비어 있거나 pq의 최상위 원소가 i보다 크거나 같으면 ret에 1을 더하고, 그렇지 않으면 0을 더합니다
최종 결괏값 ret을 반환합니다
여기서 pq의 남은 원소들이 모두 i 이상이라는 것은, 0부터 i-1까지의 순간들이 모두 전구 1~i를 켜는 데 사용되었다는 의미이므로, 해당 순간에 켜진 전구들이 정확히 1번부터 i번까지라는 것을 알 수 있습니다.
예제 (C++)
아래 구현 예제를 통해 더 잘 이해해 보겠습니다 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numTimesAllBlue(vector<int>& light) {
int ret = 0;
set <int> x;
int n = light.size();
map <int, int> m;
priority_queue <int, vector <int>, greater <int> > pq;
for(int i = 0; i < n; i++){
m[light[i]] = i;
pq.push(i);
}
for(int i = 1; i <=n; i++){
x.insert(m[i]);
while(!pq.empty() && x.count(pq.top()))pq.pop();
ret += (pq.empty() || (pq.top() >= i));
}
return ret;
}
};
main(){
vector<int> v = {2,1,3,5,4};
Solution ob;
cout << (ob.numTimesAllBlue(v));
}
입력
[2,1,3,5,4]
출력
3