백준 1406 에디터 : List를 이용해서 해결해 봅시다.

 링크드 리스트를 이용해서 간단한 편집 프로그램, 그러니까 vim과 같은 것들을 구현할 수 없을까요? 물론, 실제로 제가 구현할 것은 이것보다는 간단한 녀석입니다. 보통, 자료구조 프로젝트 때 적지 않게 하실 수도 있을 듯 싶네요.

 

 

 사실 기능은 생각보다 단순해 보입니다. 커서를 이동시킵니다.

 

 

 그리고 커서 앞에 문자를 추가시킵니다. + 앞에 't'를 추가시켰습니다. 이게 add 연산입니다. 아니면, 커서 앞에 있는 문자를 제거할 수도 있어요.

 

 

 예를 들어서, 여기에서는 ( 앞에 있는 y라는 문자를 제거했습니다. 이런 간단한 편집 프로그램은 어떻게 구성하면 좋을까요? 단, 삽입, 삭제, 커서 이동 쿼리가 최대 60만개 들어옵니다.

 

 

---

 배열은 장점이 무엇인가요? cache friendly 하다는 겁니다. 단점이 무엇인가요?

 

 

 1을 삭제해 봅시다. 그러면 어떻게 해야 하나요?

 

 

 초록색으로 칠한 부분을 앞쪽으로 1칸 이동시켜야 합니다. 59만 9999개를 말입니다. memmove를 사용하면 조금 더 빠르겠지만, O(n)인 것은 분명해 보여요. insert 연산은 어떨까요? 예를 들어, 이 배열에서, 2 뒤에 0을 추가해야 한다고 해 봅시다.

 

 

 그러면 역시 초록색으로 칠한 부분을 1칸 우측으로 옮겨야 합니다. 59만 9998개의 원소를 말입니다. 역시 O(n)인 것이 보입니다. 그런데, 문제에서는 커서 왼쪽에 있는 문자를 삭제하고, 커서 왼쪽에 문자를 추가하고, 이동하는 명령어 밖에 없어요. 또한, 커서 좌측에 문자가 삭제되거나 삽입이 될 때, 커서가 가리키는 character는 변하지 않습니다.

 

 즉, insertion과 delete가 일어나는 위치를 안다는 것이 key point라고 할 수 있어요. 그러면, List가 보다 효율적입니다. 이 친구는 연산이 일어나는 위치만 알고 있으면 insert도 delete는 그냥 포인터만 몇 개 끊어주면 되거든요.

 

 

---

 이 글에서 이중 연결 리스트에 대한 글을 보셨다고 가정하고 설명을 진행하도록 하겠습니다. 물론, 안 보셨다면, 제 블로그에도 관련 글이 있으니, 보고 오시는 것도 현명한 선택이 될 것입니다.

 

 

[관련글]

이중 연결리스트에 대해서 알아봅시다.

 

 

 먼저, 초기에, "abc"라는 문자열이 들어왔다고 해 봅시다. 그러면 다음과 같이 초기화를 합시다.

 

 

 

 head와 tail 노드는 더미 노드를 가리키고 있고, 현재 커서가 가리키고 있는, cursor 포인터는 tail을 가리키도록 합시다. 그러면 이 커서거 갈 수 있는 범위가 어떻게 될까요?

 

 

 일단 맨 끝에 있을 때, tail을 가리킬 수는 있을 겁니다. 그런데 head를 가리킬 수 있을까요? 아닙니다. 왜냐하면, 더미 노드를 가리키게 된다면 맨 앞에 있는 문자열보다 더 앞의 것을 가리키게 되기 때문입니다. 그럴 수는 없습니다. 따라서, cursor를 왼쪽으로 이동시킬 때, 커서가 가리키고 있는 위치의 prev가 head와 같다면 왼쪽으로 이동시키면 안 됩니다.

 

 마찬가지로, cursor가 tail을 가리키고 있는 경우 우측으로 이동시키면 안 되겠지요. 그러면 L과 D 명령에 대한 처리는 끝났습니다.

 

 

---

 커서 왼쪽에 있는 문자를 추가한다고 해 봅시다. 그러면 쿼리가 P $ 이런 식으로 들어옵니다. $라는 문자열을 cursor 앞에 추가한다. 이건 어떻게 하면 좋을까요?

 

 

 그러면 그림에서 b와 c 사이에 y를 추가해야 한다는 소리입니다. 그러면 b가 가리키는 노드의 next가 새로 추가된 노드를 가리켜야 합니다. 그리고 새로 추가된 노드, _new라고 해 볼게요. 이것의 next가 cursor를 가리켜야 합니다. 그런가요? 그런데 b가 있는 노드는 또 어떻게 표현할 수 있나요? cursor -> prev로 표현할 수 있지 않나요? 이것을 p라고 합시다. 이것의 next가 _new를 연결하게 하고, _new의 next가 cursor를 연결하게 하면 됩니다.

 

 

 이렇게만 하면 될까요? 현재 커서가 있는 위치의 이전 것이 _new를 가리키게 하고, _new의 이전 것이 'b'가 있는 노드를 가리키게 해야 합니다. 이것을 p라고 하면, _new->prev가 p를 가리키면 되겠군요.

 

 

 그러면 요래 연결되겠지요. 조금 더 알아보기 쉽게, 커서 전의 위치를 p라 하고, 현재 cursor의 위치를 c라고 하고, 새롭게 생성된 노드를 n이라 한다면 p의 다음 것이 n을, n의 다음 것이 c를 가리키게 합니다. 그리고 c의 이전 것이 n을, n의 이전 것이 p를 가리키게 하면 됩니다.

 

 그러면 반대로 삭제는 어떻게 하면 좋을까요? 현재 커서가 있는 위치의 이전 원소가 head이면 무시하면 되고요.

 

 

 

 그렇지 않다면, 현재 커서가 있는 노드를 C라고 한다면, C->prev가 보라색, C->prev->prev가 초록색으로 표시한 부분일 겁니다. 이를 각각 R, P라고 해 봅시다. 즉, P가 가리키는 것은 'a'가 있는 초록색, R이 가리키는 것은 'b'가 있는 보라색, C가 가리키는 것은 'c'가 있는 노드일 거에요.

 

 

 그러면 P의 next가 현재 커서의 위치인 C를 가리키게 하고, C의 prev가 P를 가리키게 바꾸면 됩니다. 그러면 보라색으로 칠한 것은 어떻게 하면 될까요? R의 next와 prev를 NULL로 업데이트 한 다음에 free 함수로 메모리 해제해 주면 될 거에요.

 

 

 별로 어렵지 않네요.