ch10-1-2(leetcode 641). 원형 데크 디자인

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 641번 ( https://leetcode.com/problems/design-circular-deque/ )

 

처음 문제를 풀었을 때는 원형 데크를 리스트를 통해서 구현했다. 하지만 문제에서는 원형 데크를 '이중 연결 리스트(doublely linked list)'를 통해서 구현하라고 명시했으므로 다시 풀어보자. 

 

이중 연결 리스트는 단일 연결 리스트(singly linked list)와 조금 다르다. 단일 연결 리스트는 포인터가 한 개로, 자신의 오른쪽에 있는 노드만 가리킬 수 있고 역방향으로는 조회할 수 없다. 반면 이중 연결 리스트는 포인터가 left, right 총 2개가 있기 때문에 자신의 왼쪽 및 오른쪽 노드를 가리키고 값을 바꿀 수 있다. 

 

class ListNode(object):
	
	def __init__(self, val=0):
		self.val = 0
		self.left = None
		self.right = None

 

1. 필드 변수

우선은 원형 데크에 필요한 필드(멤버 변수)들이 무엇인지 볼 필요가 있다. 

이전처럼 그냥 리스트로 구현할 때는 원형 큐의 길이 k를 매개변수로 받은 뒤 그만큼의 공간을 미리 초기화 및 할당해 두었고, 두 포인터(front, rear)는 리스트의 인덱스로 숫자 값을 가졌다. 큐에 몇 개의 인덱스가 있는지는 len() 함수로 간단히 계산할 수 있었다. 

 

그러나 연결 리스트의 경우 원소를 추가 및 삭제할 때 마다 길이 값을 기록해야 한다. 데크 안의 각 노드는 자신의 왼쪽과 오른쪽 노드가 누군지만 알지, 총 몇 개의 노드가 연결되어 있는지는 모르기 때문이다. 그러므로 length 값이 필요하다. 

추가할 때는 length += 1을, 삭제할 때는 length -= 1을 해 주면 되겠다. 

 

그리고 맨 앞과 맨 뒤에서 노드를 모두 접근할 수 있어야 하기 때문에 head, tail 두 개의 포인터가 필요하다. 초기 상태에서는 head의 오른쪽 노드는 tail, tail의 왼쪽 노드는 head가 되도록 포인터에 값을 할당해 주자. 

 

2. 노드 추가 & 삭제

앞의 원형 큐 문제에서는 front 포인터는 맨 앞의 원소를 가리켰지만 rear 포인터는 맨 뒤의 원소보다 한 칸 뒤를 가리켰다. 그러나 원형 데크의 경우 맨 처음에는 head와 tail 노드만 있고 해당 노드들의 값(val)은 None으로 할당해 두어야 한다. (head와 tail에 그냥 null 값을 할당하면 그 다음에 추가될 노드와 포인터를 통해서 연결될 수 없기 때문에, 값이 null인 ListNode로 할당해 두어야 한다.)

 

그러므로 만약 데크에 원소가 있는 경우, 맨 첫 번째 원소는 head 노드가 아니라 head의 오른쪽 노드가 된다. 

마찬가지로 맨 마지막 원소는 tail의 왼쪽 노드가 된다. 

 

원형 데크가 초기화된 상황을 가정하고, 여기서 노드 하나를 추가한다고 해 보자. 이때 이 노드는 head의 오른쪽, tail의 왼쪽 노드여야 한다. 

추가하려는 노드를 temp라고 하고, temp 노드를 cur 노드의 오른쪽에다 추가한다고 해 보자. 

def _add(self, cur, temp):
	right = cur.right
	cur.right = temp
	temp.left, temp.right = cur, right
	right.left = temp

 

이런 형태로 private 메소드를 만들어서 insertLast()와 insertFront()에 적용하면 코드 중복을 줄일 수 있다. 

파이썬에서는 클래스 내부 메소드의 이름 앞에 _을 하나 붙이면 해당 메소드는 외부에서는 접근할 수 없고 내부에서만 private하게 사용할 수 있다. 

 

노드를 제거할 때에도 private 메소드를 만들어서 deleteFront(), deleteLast()에 적용할 수 있다. 

연결 리스트에서는 노드를 물리적으로 제거하지 않고, 제거하려는 노드의 양쪽 노드의 포인터를 다른 노드에 할당함으로써 해당 노드를 배제시키는 방식을 사용한다. 

 

그러니까 코드를 작성할 때에도 해당 노드를 제거하는 게 아니라 해당 노드의 왼쪽/오른쪽 노드를 제거한다고 보면 된다. 

제거하려는 노드의 왼쪽 노드를 node라고 하자. 즉 실제로는 node의 오른쪽 노드를 제거하는 셈이다. 

 

편의를 위해 node의 오른쪽 노드를 A, A의 오른쪽 노드를 B라고 하자. 

A를 제거하려면, 원래 A를 가리키던 node의 right 포인터는 B를 가리키게 하고, 원래 A를 가리키던 B의 left 포인터는 node를 가리키게 하면 된다. 

def _del(self, node):
	# remove node.right
	nodeB = node.right.right
	node.right = nodeB
	nodeB.left = node