프로그래머스. 표 편집 (doubly linked list)

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

 

https://tose33.tistory.com/468

프로그래머스. 표 편집

이 문제는 예전에 c++ stl set 자료구조로 풀었던 문제인데 다시 풀었는데 효율성에서 모두 시간초과가 나왔다.

아마 내가 풀고 난 이후에 테스트케이스가 바뀐것 같다.

 

기존에 풀었던 방식으로는 사실 최악의 경우를 계산해보면 n의 최댓값이 100만이므로 표의 첫 부분과 마지막 부분에서 'Z' 연산(복구)이 반복적으로 일어난다고 하면 iterator를 첫 부분에서 마지막 부분까지 계속 이동하면서 복구 해야하기 때문에 O(n * cmd) = O(100만 * 20만)이기 때문에 충분히 시간초과가 날수 있다.

 

다시 풀어볼때 처음에는 연결리스트를 이용해야겠다고 생각해 c++ str의 <list> 자료구조를 써봤다.

이때는 시간초과의 이유가 iterator의 이동이라는 생각을 못했는데 list를 써서 시간초과가 난 이후에 깨달았다. 

결국 시간초과를 해결하기 위해서는 마지막으로 지웠던 행을 복구할때 해당 행의 위치까지 이동하지 않고 복구하는 방법이 필요했다.

 

다른 분들 코드를 봤는데 양방향 연결리스트로 이 문제가 해결된다.

양방향 연결리스트에서 노드가 삭제될때, 삭제 방법은 삭제 되는 노드의 이전 노드가 삭제 되는 노드의 다음 노드를 가르키도록하고, 삭제 되는 노드의 다음 노드가 삭제 되는 노드의 이전 노드를 가르키도록 한다.

이렇게 하면 연결리스트에서 해당 노드는 사라지게 된다. 

 

그런데 이때 연결리스트에서 지워진 해당 노드 자체는 아직 메모리에 남아있고 다음 노드의 정보와 이전 노드의 정보도 갖고있게 된다.

이 점을 복구할때 사용하면 된다. 

삭제때와 반대로, 복구할때 복구 되는 노드의 다음 노드가 복구 되는 노드를 가르키도록하고, 복구 되는 노드의 이전 노드가 복구 되는 노드를 가르키도록 하면 연결리스트에 해당 노드가 복구된다.

 

물론 노드를 지울때, 복구할때 해당 노드가 head인지 tail인지 둘 다 아닌지에 따라 처리를 조금 다르게 해야한다.

 

얼마전 열혈 자료구조 책을 완독한것이 크게 도움이 됐다. 

안봤으면 못풀었거나 엄청 힘들었을것 같다.

 

 

 

---

 

2023.11.22