[TIL] Entity의 선형 구조 / 트리 구조에 따른 구현 방식 비교 - Trouble Shooting

프로젝트를 시작하면서 Deck에 대한 기능을 맡았고, 그 기능 중 순서에 대한 로직을 parent값을 줘서 LinkedList처럼 선형 구조로 만들었다.

[TIL] parent_id로 순서 바꾸는 로직 구현

그런데 생각해 보니 이 로직은 위치 수정에 관한 로직으로 옮겨져야 했고 생성 메서드에서는 제일 오른쪽 끝에 있는 Deck의 index를 찾아 그 오른쪽에 위치시켜야 했다.

여기서 문제는 제일 오른쪽 끝에 있는 Deck을 어떻게 찾는지 였다.

---

처음 생각한 로직

일단 DB단에서 findAll()로 List의 형태로 가져오되, parent = null인 애가 제일 앞에 오도록 한다. 그 다음 새로운 자료구조를 하나 만들어서 parentId가 연결되게끔 하나하나 추가시켜준다. 그리고 마지막 Deck을 찾아 그 deck의 Id를 찾는다.

근데 이렇게 할 경우 최대 O(n2)이 걸리게 된다.

쿼리로 바로 DB단에서 마지막 값을 찾아서 가져올 수는 없을까 하고 생각하다가 쿼리에 대한 이해가 부족하여 튜터님께 여쭤보러 갔더니 connected by와 level(재귀 쿼리)을 이용하시면 될거라고 하셨다.

그 다음에 튜터님은 또 한 마디 하셨는데 connected by와 level을 사용하여서 구현하면 시간복잡도가 O(n)이라고 하셨다. 

그러고 말씀해주신 것이 이런 식으로 parent를 줘서 Entity의 구조를 만들 때는 보통 트리 구조일 때, 즉, 내가 전에 구현했던 대댓글 구조일 때 많이 쓴다고 한다. 어떤 선형 구조일 때는 이런 식이 아니라 전 글에 자료에 있었던 내용처럼 position 필드에 큰 값을 부여하여 중간값을 찾는 식으로 많이 구현한다고 하셨다.

그래서 다시 다른 방법으로 구현을 해 볼까 하다가 일단은 parent로 구현을 해보기도 했고 해서 리팩토링 과제로 남겨두기로 하였다!