코드 그라운드 Rectangles문제를 풀면서...

음 이 문제는 종만북의 트리단원에 나와있는 요새라는 문제처럼 풀려고 했다.
먼저 여유있게 가장 큰 네모로 둘러싸고 그 네모를 root로 하는 트리를 만들되, 어떤 부모 노드의 자식이 되려면 자식 네모가 부모 네모가 둘러싼 다른 네모들에 포함되지 않고, 부모 네모에 포함될 경우 부모 노드의 자식으로 해서... 트리를 만들면 만들어진다.

처음에는 양방향으로 트리를 만들다 보니... 원래 종만북의 문제나 BOJ 어린왕자 문제같은 경우는 양방향으로 만들어도 괜찮은 것이, 원끼리 겹치는 것이 없기 때문에 한 노드는 부모를 하나만 가지는데, 이 문제의 경우 겹치는 것이 있어서 한 노드가 부모를 여러개 가질 수 있다. 그래서 양방향으로 하면 런타임 에러를 받는 것 같다. 그래서 부모가 자식만 가리키도록 트리를 만들었더니 런타임 에러는 안나고 TLE를 받았다. 아 그리고 참고로 부모가 자식만 가리키게 단방향으로 해도 이 문제는 트리를 만들고 트리의 높이를 구하면 되는 문제이기 때문에 괜찮다.

시간초과... 일단 k가 50개 이하일 때, 즉 사각형이 50개 이하로 입력으로 들어올 때는 통과하는데, 그보다 큰 데이터에 대해서는 시간초과였다.

그래서 풀이도 좀 찾아보고, 공유된 코드를 봤다. 대부분 dp로 풀었는데, 공유된 코드를 보니, 굳이 트리를 만들 필요가 없었다는 걸 깨달았다. 난 종만북의 코드처럼 트리를 만들고, 트리를 탐색했는데, 그냥 트리를 만드는 과정에서 높이를 구하면 된다...(종만북에도 그런 말이 있었는데, 그 때는 이해를 못했지만 지금 깨달았다...) 그래서 그렇게 했는데 역시 시간초과... 근데 내가 높이를 구하는 과정도 결국은 dp랑 비슷해 보였다. 아니 정확히 말하면 높이를 구할 때, dp를 쓰면 더 빨라질 것 같았다. 음 근데 나는 dp랑은 좀 다른 것이, 어떤 노드의 자식이 될 수 있는 노드만 O(n)만큼 시간을 들여서 선별하기 때문에 괜찮지 않을까...(dp로 하는 경우 직계자식이 될 수 있는 경우만 보는 것이 아니라 모든 경우를 다 본다) 하고 생각했지만...

아까 위에서 말했듯이, 내 방식대로 하면 트리가 만들어짐에도 그렇게 느린 이유는 바로 겹치는 사각형들이 있고 그 겹친 사각형들에 공통으로 포함된 사각형들이 존재해서 서로 다른 노드가 같은 노드를 자식으로 가질 수 있게되고 트리의 노드 개수가 k개가 아니라 훨씬 커질 수 있는 것이다... 결국 내 방식대로 하더라도 memoization을 이용하는 게 도움이 된다.

그래서 memoization을 적용해봤는데, 그래도 시간초과...
근데 시간복잡도를 계산해보면 난 직계자식인지 아닌지 판단하기 위해 isChild함수를 호출해서 O(n)이긴 하지만 좀 복잡하게 확인하는데 결국 O(n)이고 모든 노드에 대해 isChild함수를 호출하다 보니 d배열의 크기는 n이고.. 그러니까 결국 O(n세제곱)의 시간복잡도가 되는 것이었다...!!! 헉...

그렇다. memoization을 쓸것이므로 포함되는지만 살펴보는 enclose함수만 써주면 O(n제곱)만에 가능하다... 결국 어쩌다 보니 공유코드에 있는 분들의 코드와 똑같은 코드가 되어가고 있었다. 조금 다른 점이라면 난 매우 큰 네모를 만들어서 root로 놓고 거기서부터 시작해서 좀 편하게 한 것 정도...?..

그런데 또 시간초과.. 혹시나 해서 max를 없애고 그냥 < 비교를 통해 최대값을 갱신해봤는데, 아슬아슬하게 통과했다... 아 STL이 느리네... 음 혹시나 해서 enclose함수를 지우고 그냥 그 안의 내용을 직접 if문에 옮겼더니 0.1초 정도 더 빨라졌다.. 여유있게 통과.. 아...
enclose함수에 parameter가 복사되고 그러느라.. 시간이 좀 더 걸린건가..

어쨌든 공유코드를 보고 맞긴 맞았는데... 나름 깨달음을 얻게해준 문제였다.
이 문제는 종만북 처럼 트리의 지름을 구하는 문제가 아니기 때문에.. 굳이 트리를 쓸 필요도 없을 뿐더러, 특히 겹치는 부분이 나오기 때문에.. 트리를 만들더라도 노드의 수가 매우 늘어나서 시간초과가 난다!! 그래서 memoization을 이용해야 하고 O(n제곱)으로 구현할 수 있다.

그리고 좀 뒷통수 맞은 기분이기 한데 dp로 보면 별거 아닌 것이..
d[parent]= parent사각형부터 시작해서 겹치지 않고 포함되는 사각형의 개수 라고 하면,
d[parent]= MAX(d[child]+1) 이 될 것이다. child는 parent에 완전히 포함되는 사각형일 것이고... child사각형이 포함하는 사각형은 결국 parent사각형에도 포함될 것이므로...

아 생각도 못했었는데...여튼 공부가 많이 된 좋은 문제였다.