웹 프로젝트 PAT - 09. 책 목차 정렬하기 알고리즘

책 목차 정렬하기

DB상에 저장된 책의 목차들을 사용자에게 보여주기 위해서는 아래와 같은 조건이 있다.

• 목차는 상위 목차를 한개 가질 수 있다.
• 목차는 하위 목차를 여러개 가질 수 있다.

위와 같은 조건만 있다면 답글이 달리는 '계층형 게시판'을 구현 할 때 사용 한 알고리즘이면 충분했다. 하지만 책 목차와 게시판의 결정적인 차이점은 게시판은 글간의 위치가 수정되는 경우가 거의 없지만, 책 목차를 관리하는 관리자 입장에서 순서가 변경 될 수 도 있기 때문이다. 예를들어 한 목차가 다른 목차와 순서를 바뀌게 되면 그의 하위 목차들도 모두 따라가야 한다. (대신 순서를 바꾸는건 같은 depth의 목차만 바꿀 수 있도록 한다.)

이를 해결하기 위한 방법으로 3가지가 고려 되었다. 공통적으로 목차가 어느 수준의 목차인지 구분하는 depth, 같은 depth간의 순서를 구분해주는 sequence필드는 가지고 있다. depth는 대분류는 0, 그 아래 중분류는 1 이런식으로 들어간다.

1. 대분류, 중분류, 소분류를 구분하는 id값을 필드로 갖게 한다.
2. 순서를 결정하는 sequence를 아주 큰 정수나 소수로 나타낸다. 예를들어 sequence가 1-2-3-4로 들어가 있는 경우 4를 1과 2사이로 옮기게 되면 sequence를 1.5로 설정한다.
3. 바로 위의 상위 목차 id만을 가지고 있고 부모-자식간의 셀프 참조가 되어 있는 방법

1번 방법은 구현하기 쉽다. 하지만 분류가 3가지 이상 인 경우 유연하게 대처할 수 없고, 위치 변경시에 update해야 하는 필드가 여러개 있다는 단점이 분명했다.

2번 방법도 구현하기 어렵지 않고. 분류가 여러가지 인 경우도 유연하게 대처할 수 있지만, 잦은 위치 이동시에 필드값이 매우 지저분하게 들어가는 단점이 있다.

3번 방법은 셀프 참조(조인) 방식이기 때문에 필드 값이 깔끔하고 직관적이다. 그리고 분류의 단계가 여러개 인 경우도 유연하게 대처 할 수 있다. 문제는 정렬하기가 매우 어렵다. 

최대한 3번 방법을 통해서 구현하고 싶다는 생각에 알고리즘을 고민하기 시작했고, 꽤 오랜 시간을 할애한 끝에 적절한 알고리즘을 찾을 수 있었다.(ㅠㅠ) 대신 앞으로 비슷한 문제를 해결하는 데 좋은 경험이 된 것 같아 시간이 마냥 아깝지만은 않았다.

정렬 알고리즘

1. DB에서 책 목차들을 불러오는데 정렬 방식을 depth의 오름차순, sequence의 오름차순으로 불러온다.

DB에서 가져온 데이터	정렬 하기 원하는 방식
PART 1 언어능력	PART 1 언어능력
PART 2 수리능력	CHAPTER 01 어휘
PART 3 추리능력	유형1 유의어
CHAPTER 01 어휘	유형2 다의어
CHAPTER 02 독해	유형3 단어관계
유형1 유의어	CHAPTER 02 독해
유형2 다의어	PART 2 수리능력
유형3 단어관계	PART 3 추리능력



2. 서비스 내에서 정렬을 담당하는 메소드를 따로 작성한다.
3. 가져 온 책 목차들을 위에서 부터 검사하면서 적절한 위치로 삽입된다. 예를들어 'CHAPTER 01 어휘'는 부모인 'PART 1언어능력' 밑에 삽입 되어야 한다. 'CHAPTER 01 어휘'를 삭제하고 적절한 위치에 삽입한다. 'CHAPTER 02 독해'는 부모인 'PART 1 언어능력' 밑에 삽입 되어야 하지만 sequence가 'CHAPTER 01 어휘'보다 한칸 뒤에 위치 해야하므로 삽입 위치를 sequence로 판단한다.

위와 같은 로직이면 간단히 책목차를 정렬할 수 있다. 하지만 이렇게 삽입하게 되면 밑에 있는 요소들이 한칸 씩 밀리게 되는데 이런 경우 LinkedList가 ArrayList보다 훨씬 빠르고 효율적으로 진행되므로 마지막에 LinkedList를 떠올린게 신의 한수 였다. (자료구조의 중요성을 몸소 느낀 소중한 기회였다.)

구현 코드 (java)

private List sortBookContents(LinkedList bookContentList) {
    BookContent tmpBookContent;
    for (int i = 0; i < bookContentList.size(); i++) {
        BookContent bookContent = bookContentList.get(i);
        BookContent superBookContent = bookContent.getSuperBookContent();
        if (superBookContent != null) {
            tmpBookContent = bookContent;
            bookContentList.remove(bookContent);
            bookContentList.add(
                    bookContentList.indexOf(superBookContent) + 1 + bookContent.getSequence(),
                    tmpBookContent);
        }
    }
    return bookContentList;
}