지난주와 지지난주 합쳐 3 문제를 풀어볼 수 있었다.
배열과 window의 크기가 주어졌을 때 window 내부의 최솟값을 모든 circular 배열에 대해서 구하는 문제
2차원 좌표상에서 2*2로 사각형 구간들이 주어졌을 때 사각형이 겹칠 수 있다는 가정에서 모든 사각형의 넓이의 합을 구하는 문제
연속된 size 2 배열을 주고 조건에 맞게 최대값과 최솟값을 구하는 문제 등..
3가지의 문제를 풀어보았고
1주차에는 2개는 답은 맞췄지만 Time Complexity를 해결하지 못하였고 1개는 풀지 못했다.
2주차에는 Time Complexity 관련 설명을 들은 후에 문제를 해결할 수 있었다.
최대값과 최소값 문제 같은 경우에는 최대값과 최소값을 구하는 Sort를 실행하는 것이 문제가 된다.
n번의 시도에 대해서 k번의 (k <= n) sorting이 발생하는 것도 전체적으로 속도를 크게 저하시킬 수 있는 요인이다. (sorting은 보통 O(nlogn))
때문에 Sort를 하지 않고 저장소에 대한 Update를 짧은 시간내에 한다는 발상이 필요하다.
우리가 n번 update를 한다고 했을 때, Segment tree나 RBT, min_max heap을 사용하면 O(logn), O(1) 시간안에 관련된 최대값, 최소값을 구할 수 있는 함수가 존재한다.
c++의 set이 RBT로 구현되어 있다는 것을 확인하고 문제의 조건에 맞게 multiset을 활용하여 데이터를 관리하였고, rbegin, begin으로 최대 최소를 제거할 수 있었다.
Window 문제 같은 경우에는 window를 매번 계산하지 말고 update를 하는 방법으로 시간을 단축시켜야 했다. 그렇기 때문에 window의 자료를 담아둘 데이터 구조가 필요했고, 강의에서는 이를 Deque 또는 Segment Tree 형태로 자료를 저장하면 window의 입출력이 있을 때의 최소값을 찾는 행위의 시간 복잡도를 보장할 수 있다고 하였다.
사실 더 쉬운 구현을 위해 Deque의 형태로 구현을 하였으며, 3개의 문제 중에서는 자료구조가 직관적이고 룰베이스로 해결할 수 있었기 때문에 가장 빠른 시간안에 해결할 수 있었다.
사각형의 넓이를 구하는 문제는 한쪽 축을 level 축으로 정해서 [0, 10]과 같은 경우 level 0 ~ level 9를 모두 포함하는 구간으로 정한다.
반대쪽 측은 interval 축으로 정해서 2-D array에 interval을 계속 저장을 한다.
문제를 간단하게 만들어서 생각하면 결국 level 6에 [3,5] 구간이 존재한다면 실제로는 [[6, 7], [3, 5]]가 존재하는 것과 같다. 모든 사각형을 위와 같이 분해하여 map에 담아두기만 하면 해당 문제는 결국 interval의 중복을 허용하며 중첩시키는 문제와 같다. 이를 모든 level에 대해서 수행하는 것 뿐이다.
다만 해당 방식으로 해결한다고 했을 때, level에 해당하는 축의 길이에 해당하는 for-loop를 돌아야 함으로 굉장히 오래 걸릴 것으로 예상되며 각각의 루프가 내부에 저장한 interval의 길이 만큼의 루프를 다시 돌아야 한다.
시간 복잡도가 O(n^2)일 것 같은데.. 더 줄일 수 있는 방법을 생각해 봐야 할 것 같다.
