event driven : ps 문제에서 간단하게 활용해 봅시다.

 이벤트를 넣어두고 그것을 활용한다. 작년에 스터디를 하면서 처음 들어본 말이였습니다. 사실, Java에서 mouse event listener와 같은 것이나 call back 패턴에서만 쓰이는 줄 알았기 때문입니다. 그런데, 특정 문제에서 이것을 잘 활용하면 생각보다 간단하게 풀 수 있습니다.

 

 

---

 Egg라는 문제를 보도록 하겠습니다. 이 문제를 간단하게 설명하면 아래와 같습니다.

 

 생각보다 쉽지 않습니다. 그런데, 점들이 삭제되거나, 생성되는 이벤트가 주어지지 않으므로, 다음의 발상을 생각해 볼 수 있습니다.

 

 

 사실, 이것만 계산을 하면, 문제에서 요구하는 쿼리도 해결할 수 있습니다. 이것을 어떻게 해결하면 좋을까요?

 

 

 보라색 영역에 점이 있다고 해 보겠습니다. 우리는 x좌표가 A 이하이고, y 좌표가 B 이하인 점들의 갯수를 구하고 싶습니다. 그런데, 답을 순서대로 계산하지 않아도 된다면, (A, B)쌍의 쿼리를 따로 저장한 다음에, A 오름차순으로 정렬하면 됩니다. 그러면 어떻게 구할 수 있는지 보도록 하겠습니다.

 

 

 x를 기준으로 정렬했다면, 이벤트를 event_point[x'].push_back(y')로 생성하겠습니다. 이는 x의 값이 x'일 때, y'에 점이 있다는 이벤트 (혹은 트리거) 를 나타냅니다. 그 다음에 어떻게 하면 좋을까요?

 

 

 x좌표가 0인 것들부터 훑겠습니다. x값이 0인 점들은 event_point[0]에 들어 있습니다. 이 그림에서는 (0,3)이 들어 있습니다. 이 점을 만났을 때, 우리가 수행할 연산은, 자료구조에 3이라는 count를 하나 증가시킨다입니다.

 

 

 이렇게 말입니다. 그러면 x좌표가 0이하이고, y좌표가 4이하인 점들의 갯수는 몇 개일까요? 0 + 0 + 0 + 1 + 0 = 1개입니다. x 좌표가 0 이하이고, y 좌표가 2 이하인 점들의 갯수는? 0 + 0 + 0 = 0개입니다. 여기까지 끝난 시점을 S(0)이라 하겠습니다.

 

 

 이제 x가 1인 것들을 볼 겁니다. (1,1)이 있습니다. x좌표가 1일 때, y좌표가 1인 이벤트가 있습니다. 그러면 count[1]의 값을 하나 증가시키면 됩니다.

 

 그러면 제가 설정한 이벤트에 의해서, 자료구조는 다음과 같이 업데이트가 될 겁니다. x좌표가 1 이하이고, y좌표가 2이하인 점은 몇 개인가요? 1개입니다. 0 + 1 + 0은 1이기 때문입니다. x값이 1이하이고, y값이 3 이하인 점은 0 + 1 + 0 + 1 = 2개입니다. 여기까지 업데이트 한 상태를 S(1)이라 하겠습니다.

 

 

 다음에 x = 2일 때 그 값을 반영해 보겠습니다. (2,2)가 있으므로, event_point[2]에는 2만 들어있습니다.

 

 

 그러면, count[2]값이 하나 증가합니다. 이 시점에 x 좌표의 값이 2 이하이고, y 좌표의 값이 t 이하인 점의 갯수는? 에 대한 쿼리에 답을 하시면 됩니다. x 좌표 값이 1이하이고 y값이 t' 이하인 point의 갯수를 구하는 쿼리는 어느 시점에 답을 하면 될까요? S(1)이 끝난 시점에 답을 하시면 됩니다. 이런 식으로 x 좌표를 0부터, 문제 범위인 10^5까지 모두 보면서 x좌표가 x'이하이고, y좌표가 y'이하인 점의 갯수를 구하라는 쿼리에 offline으로 답을 하시면 됩니다.

 

 우리는 x가 어떠한 값일 때, 들어오는 점들이 '추가'되는 것을 이벤트로 보았습니다. offline Query에 대한 내용은 설명을 잘 해주시는  고수 분들이 많으니 여기서 따로 언급하지는 않겠습니다. 그냥 간단하게 알고 싶으시다면, 업데이트의 결과를 즉각적으로 답할 필요가 없을 때 쓰는 수단 정도로 생각하시면 좋습니다.

 

---

 다음 문제를 생각해 보겠습니다.

 

 단, k값은 정수라고 해 보겠습니다. 이런 문제는 요새 코딩 테스트에서도 꽤 자주 나오는 패턴입니다. 상당히 어려워 보이는데요. 어떻게 풀면 좋을까요?

 

 

 예를 들어, 3번째 선분이 (1,3), (4,3)를 잇는 친구라고 해 보겠습니다. x = k 입장에서 보았을 때, k < 1이라면, 이 선분과 만나지 않을 겁니다. 만약에 k = 1이면 어떨까요?

 

 

 해당 선분과 만나기 시작합니다. 즉, k값이 1일 때, 해당 선분과 만나는 이벤트가 활성화가 됩니다. 대충 add_event[1]에 선분 3을 넣어놓습니다.

 

 

 k값이 쭉 커지다가 어느 시점부터 만나지 않을까요? k값이 5가 되었을 때 부터입니다. del_event[5]에 선분 3을 넣겠습니다. 이는 k값이 4일 때부터 선분 3과는 만나지 않는다는 것을 의미합니다. x = k'과 만나는 선분의 갯수가 몇 개인가라는 쿼리가 Q개 들어왔을 때, k'을 오름차순으로 정렬한 다음에, add_event와 del_event를 적절히 적용해 가면서 만나는 선분들을 관리해 주면 무난하게 해결할 수 있음을 알 수 있습니다.

 

 그런데, 조금 더 관점을 바꾸어서 생각해 보면, 결국 x가 어떠한 특정 값부터 이벤트를 누적해 온다는 것을 알 수 있어요. 그러면, 이를 누적 배열로 관리해도 될 거에요.

 

 

 k값이 1일 때, 선분이 추가되니까 count[1]에 +1을 더해줍니다. 다음에 k값이 5가 되었을 때 제거가 되니, count[5]에 1을 빼 줍니다. 결국, 이렇게 해도, 추가되고 제거되는 event를 누적시키는 관점은 같습니다.