Flatten a Multilevel Doubly Linked List
계층으로 된 double linked list를 1차원으로 펼쳐야 하는 문제.
처음 접근 방법 -> recursive 한 방법을 사용하여, 가장 아래단계까지 접근 후 되돌아 오는 방식.
기본 아이디어
1. 해당 노드가 child를 가지고 있을 경우, 아래 단계의 마지막 노드를 리턴 후, 원래 노드의 다음과 연결해준다.
2. 해당 노드가 child를 가지고 있지 않는 경우, 해당 줄에서 child를 가지고 있는 노드를 찾을 때 까지 이동 후, 이를 리턴한다.
간단해 보였는데, 생각보다 애를 먹었던 부분.
1. Node* 를 리턴해야 하는 함수에서, 적절한 리턴값을 정하지 못하던 부분.
-> Ex) 마지막 노드를 리턴해야하는데, 반복적으로 끝에있는 null까지 탐색하여 nullptr error를 보았음.
2. child가 있는 부분에서, 적절한 리턴값을 받은 뒤, 현행 node를 어디로 이동해야하는가에 대한 부분.
-> 한줄에 하나의 node만 child를 가지기에, 아래단계의 child 처리 후 움직이지 않아도 될 것이라 생각해서 node = flatten(node->next) 등으로 받거나, child와 non-child에 대한 case를 if/else-if로 나누었음. 1번 문제와 함께 null을 리턴하는 부분에서 문제 발견이 늦어짐.
최초 Accept 된 코드.
개선 가능했던 부분
1. flatten 함수의 예외처리 부분
2. dummy 설정 부분
3. recursion을 사용하긴 하였으나, 직관적이지 않음.
if(head->next)에서 불필요하게 많은 함수 호출이 발생.
개선 후 Accept 된 코드
개선 사항.
1. 한 layer에서 한번의 funcion call만 발생하도록, 함수 내부 while문 사용.
2. prev와 head를 두어, 가장 마지막 node를 수월하게 return 할 수 있도록 함.
3. 예외처리 및 dummy제거.
또 다른 관점으로의 접근 방법
재귀적으로 아래 단계를 다 돌아와야하는 방법과 달리, 매번 chile가 있는 노드를 만나게 되면, 그 다음줄을 통째로 이번줄에 통합시키는 방법이 있었음.
실행시간은 확인을 하지 않았으나, 메모리 측면에서 재귀적인 함수 사용을 하지 않기에 우수한 성능을 보이는 것 확인.
그런데 실행 속도는 최초 돌린 코드가 0ms로 압도적으로 빨랐음.
앞으로 고려 할 점.
1. linked list를 다루는 경우 base case를 무엇으로 둘건가
null을 마지막으로 return 할건가? vs 마지막 node를 return할 건가?
2. 재귀 코드 작성 훈련.
