아스

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

leetcode 347번 ( https://leetcode.com/problems/top-k-frequent-elements/ )

풀이 1. 

collections 라이브러리의 Counter 자료형에서 기본으로 주어지는 메소드만으로도 풀 수 있다. 

Counter 객체를 초기화할 때 매개변수로 문자열이나 리스트를 넣을 수 있다. Counter 클래스는 딕셔너리의 하위 클래스라서 딕셔너리의 기본 기능들은 다 가지고 있다. 다만 문자열의 문자나 리스트의 개별 원소를 key 값으로, 해당 문자나 원소의 등장 빈도를 value로 갖는다. 

counter = collections.Counter(nums)	# initialize Counter object

Counter 클래스의 most_common(k) 메소드를 사용하면 Counter에 저장된 key-value pair 중 가장 등장빈도(value)가 높은 쌍을 총 k개 리턴한다. 

리스트 형태로 리턴하고, 리스트의 각 원소는 (key, value)로 된 튜플(tuple) 형식이다. 

return counter.most_common(k)
# [(1,4), (2,3)] (when 1 appeared 4 and 2 appeared 3 times)

list comprehension을 통해서 이 튜플-리스트를 key만 들어있는 리스트 형태로 바꿔 주면 된다. 

(key는 튜플의 0번째 인덱스이다.)

전체 코드는 다음과 같다. 

class Solution(object):
	def topKFrequent(self, nums, k):
		counter = collections.Counter(nums)
		return [mc[0] for mc in counter.most_common(k)]

풀이 2. 

풀이 1번에서 맨 마지막에 for loop로 리스트 컴프리헨션을 사용하지 않고, zip()을 사용해서 더 간단히 풀 수 있다고 한다. 

zip() 함수는 여러 개의 리스트를 병렬적으로 묶어 준다. 

nums = [1,2,3]
alphabets = ["a","b","c"]

for z in zip(nums, alphabets):
	print(z)
    
# [1, "a"]
# [2, "b"]
# [3, "c"]

풀이 1번의 코드를 이렇게 바꿀 수 있다. 

class Solution(object):

    def topKFrequent(self, nums, k):    
        counter = collections.Counter(nums)
        return list(zip(counter.most_common(k))[0])

풀이 3. 

Counter 변수는 리스트의 값과 발생빈도를 저장하는 용도로만 사용하고, 힙에다가 Counter에 있는 값들을 저장 및 정렬해서 하나씩 총 k개를 빼는 방법도 있다. 힙을 사용할 때는 priority-queue와 heapq 라이브러리 등 여러 라이브러리가 있지만 thread-safe로 인한 locking 오버헤드 문제 때문에 여기서는 heapq 라이브러리를 사용한다. 

힙에 counter의 원소들(key-value 한 쌍)을 넣을 때는 heappush() 메소드를 사용한다. 

heapq.heappush(heap 변수, heap 변수에 넣을 값)

값을 넣을 때는 counter 객체에서 자동으로 계산해 준 등장 빈도(value)를 음수로 바꿔서 넣는다. heapq는 min heap만 제공하기 때문이다. 

(정확히는 max heap도 제공하지만 해당 메소드는 protected 메소드라서 직접 접근하는 것은 권장하지 않는다.)

힙에 저장된 원소들을 제거할 때는 heappop() 메소드를 사용한다. 매개변수를 받지 않으며, heap에 저장된 값을 정렬한 뒤 가장 작은 원소부터 리턴한다. 

heapq.heappop()

이후 heappop()으로 힙에서 정렬된 원소들을 총 k번 빼 주고, heappop()을 통해 힙에서 제거되어 반환된 key-value 쌍은 리스트에 저장해 주자. 

참고한 포스트

https://docs.python.org/3/library/collections.html

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

leetcode 3번 ( https://leetcode.com/problems/longest-substring-without-repeating-characters/ )

풀이 1. 

시간 복잡도의 제한이 없다면 for loop를 2번 사용하면 간단히 풀 수 있다. 

start의 값을 정한 뒤 해당 위치보다 뒤에 있는 문자열들을 전부 돌면서 이전에 나왔던 문자열과 겹치지 않으면 count를 1씩 증가시키고, 겹친다면 for loop에서 탈출한다. 따라서 총 시간 복잡도는 O(n^2)이다. 

전체 풀이는 다음과 같다. 

class Solution(object):

    def lengthOfLongestSubstring(self, s):
    
        maxCount = 0
        for i in range(len(s)):
            strs = ""
            for string in s[i:]:
                if string not in strs:
                    strs += string
                else:
                    break
            maxCount = maxCount if maxCount > len(strs) else len(strs)

        return maxCount

풀이 2. 

교재에서는 더 간단히 풀 수 있는 방법을 제시한다. 바로 for loop를 두 번 도는 대신 투 포인터를 이용해서 for loop를 한 번만 도는 것이다. 

이전에 나왔던 문자열인지를 확인하는 작업이 필요한데 여기서는 딕셔너리 변수를 해시맵으로 사용해서 이전에 나온 문자열인지를 확인한다. 

포인터 하나(index, string)는 전체 문자열을 돌면서 해당 문자열이 해시맵(used)에 포함되어 있는지를 체크한다. index는 현재 탐색하는 문자열의 위치를, string은 현재 탐색하는 문자열 자체를 값으로 갖는다. 

나머지 포인터 하나(start)는 문자열이 시작하는 기준점을 가리킨다. 

또한 maxCount 변수도 선언해서 최대값을 계속 업데이트 할 수 있도록 한다. 

maxCount = max(maxCount, other_value)

해시맵 used는 문자열을 key로, 해당 문자열의 위치를 value로 갖는다. 문자열을 순회하다가 이전에 있던 문자열이 다시 등장하면 값을 수정한다. 

used[string] = index

예를 들어서 'a'라는 문자가 1번째 인덱스(앞에서 두 번째)에 있는 경우는 다음과 같다. 

만약 index 포인터가 가리키는 문자열(string)의 값이 이미 used에 포함되어 있고, 문자열의 위치 값도 start 포인터 값보다 크다면 해당 문자열은 중복된 문자열이다. 

예를 들어서 "abcabcbb" 를 탐색한다고 가정하자. 

현재 start(문자열이 시작하는 기준점) 값은 2라고 두면, 'c'부터 문자열이 시작한다고 보면 된다.

그리고 index(순회하는 문자열의 기준점) 값은 5라고 두자. 그러면 index는 두 번째 'c'를 가리키고 있다. 이때 해당 문자열의 위치 값은 5로, start 포인터 값인 2보다 크다. 즉 첫 번째 c를 시작점으로 두고 탐색하고 있는데 두 번째 c가 나온 것이므로 중복 문자열이 나온 것이다. 

그럴 땐 start 포인터의 값을 현재 탐색하고 있는 문자열의 위치 + 1로 바꿔 준다. 

start = used[string] + 1

만약 아니라면 count 변수의 값을 비교해서 1 증가시킨다. 

4번째 경우도 마찬가지로, 첫 번째 'a'에서부터 탐색을 하고 있는데 두 번째 'a'가 등장했으므로 중복 문자열이 나타난 상황이다. 이 경우 used[a]의 값도 새로 변경되고, 0이었던 start 값도 3으로 바꿔 준다. 

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

leetcode 771번 ( https://leetcode.com/problems/jewels-and-stones/ )

풀이 1 : Counter

(교재를 참고하지 않은 풀이입니다.)

해시맵 단원의 문제인만큼 해시맵을 사용해서 풀 수 있다. 

파이썬의 딕셔너리 자료형은 내부적으로 해시맵으로 구현되어 있다. 또한 파이썬에는 딕셔너리를 상속받은, 즉 딕셔너리의 하위 클래스인 다른 클래스들도 있는데, 이 클래스들은 (key, value) 한 쌍을 저장하는 딕셔너리의 기본 특징에 더해서 추가적인 기능이 있다.

딕셔너리의 하위 클래스로는 Counter가 대표적이다. 

Counter는 초기화할 때 리스트나 문자열을 매개변수로 받을 수 있다. 이 경우 리스트나 문자열에 포함된 원소가 key, 해당 원소가 몇 번 나타났는지가 value가 된다. 그래서 문자열의 등장 빈도를 알고 싶다면 Counter으로 간단하게 계산할 수 있다. 

우선 stones 문자열을 매개변수로 사용해서 Counter 객체를 만들어 준다. 그러면 그 Counter 객체는 stones의 각 문자열을 key 값으로, 해당 문자열의 등장 빈도(숫자)를 value로 갖는다. 

또한 없는 문자열을 조회하려고 한다면 오류를 발생시키지 않고 0을 리턴한다. 

그리고 jewels에 대해 for loop를 돌려서, 각 jewels 알파벳의 value 값(=등장 빈도)를 모두 더한 뒤 리턴한다. 

전체 코드는 다음과 같다. 

class Solution(object):

    def numJewelsInStones(self, jewels, stones):
    
        counter = collections.Counter(stones)
        count = 0
        for j in jewels:
            count += counter[j]
        return count

풀이 2: 리스트 컴프리헨션(List Comprehension)

교재에서는 이 코드를 한 줄로 정리하는 방법도 제시한다. 

list comprehension을 이용하면 짧은 코드로 기존 리스트(jewels, stones)의 값을 이용해서 새 리스트들 만들 수 있다. 

def solution(self, jewels, stones):
	return sum(s in jewels for s in stones)

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

leetcode 706번 ( https://leetcode.com/problems/design-hashmap/ )

풀이 1. 

(leetcode에서 정답 처리되었으나 hash collision이 발생하는 경우를 처리하는 로직이 없어서 수정이 필요한 풀이입니다. 풀이 2에서 hash collision 처리 로직을 포함하였습니다.)

문제에서는 해시맵(hashmap)의 크기나, hash collision이 발생했을 때 어떤 방식으로 대처할지 등을 제시하지 않았다. 그러므로 임의로 크기를 할당하면 된다. 

put()으로 해시맵에 (key, value) entry를 넣으려면 해시 함수(hash function)를 만들어야 한다.

해시맵의 key, value는 모두 정수형이므로 가장 간단한 방식으로는 key값 mod hashmap size를 해시 함수로 둘 수 있다. 

def put(self, key, value):
        index = key % self.size		# hash function
        self.hashMap[index] = value

전체 코드는 다음과 같다. 

class MyHashMap(object):

    def __init__(self):
        self.size = 10 ** 6
        self.hashMap = [None] * self.size

    def put(self, key, value):
        index = key % self.size
        self.hashMap[index] = value
        

    def get(self, key):
        index = key % self.size
        if self.hashMap[index] is None:
            return -1
        return self.hashMap[index]
        

    def remove(self, key):
        index = key % self.size
        if self.hashMap[index] is not None:
            self.hashMap[index] = None

풀이 2. 

위의 풀이는 hashmap을 일반 리스트로 구현하였다. 하지만 collections 라이브러리를 사용해서 딕셔너리로 구현한다면 해시맵에 없는 키를 조회했을 때 오류가 나지 않고 자동으로 새 값을 만들  수 있다. 

self.hashMap = collections.defaultdict()

위의 풀이도 정답으로 처리되지만 hash collision이 일어날 경우를 처리하지 않는다. 

예를 들면 size=10인 해시맵에 (7, 20), (17, 30) 두 개의 entry를 put()으로 넣는다고 해 보자. 

hash collision을 처리하지 않은 위의 경우는 key=7을 get()으로 조회하였을 때 20이 아닌 30을 리턴한다. 

7 mod 10 = 7, 17 mod 10 = 7로 key 깂이 같아서 hashmap[7]의 값이 20에서 30으로 대체되었기 때문이다. 

만약 hash collision을 개별 체이닝(separate chaining) 방식으로 처리한다고 가정한다면 hashmap[7]을 조회하면 20, hashmap[17]을 조회하면 30이 나온다. 교재를 참고해서 수정해 보자. 

open addressing

교재에서도 separate chaining 방법을 사용해서 hash collision에 대처하고 있다. 개별 체이닝 방법 말고도 오픈 어드레싱(open addressing) 방법이 있다. 하지만 이 방법은 hash collision이 발생할 경우 선형 탐색(linear probing)이나 다른 해시 함수를 추가로 사용해야 하며 clustering(같은 bucket(인덱스) 값을 가진 entry들이 서로 뭉쳐서 분포하는 현상) 등의 문제가 있기 때문에 사용하지 않은 것으로 보인다. 

separate chaining

separate chaining은 hash collision이 발생했을 때 하나의 bucket을 연결 리스트로 연결해서 bucket 값은 같고 key 값은 다른 entry들을 계속 연결한다. 이 방법은 open addressing처럼 hash collision을 발생시킨 entry를 어느 자리에 추가로 배치할지를 고려하지 않아도 된다는 장점이 있다. 반면 해시 함수가 들어오는 entry들을 고르게 분포시키지 못할 경우 탐색 시간이 최대 O(n)만큼 걸릴 수 있다는 단점도 있다. 

separate chaining을 사용하려면 개별 entry가 들어올 때마다 노드를 생성해야 한다. 그래야 포인터를 통해 연결 리스트를 탐색할 수 있다. 

연결 리스트의 경우 보통은 단일 연결 리스트(singly linked list)로 구현한다. 

class ListNode(object):

	def __init__(self, key=None, value=None):
		self.key = key
		self.value = value
		self.next = None

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

leetcode 23번 ( https://leetcode.com/problems/merge-k-sorted-lists/ )

풀이

교재의 방법처럼 우선순위 큐(priority queue)를 사용하면 쉽게 풀 수 있는 문제다. 

기존의 큐는 먼저 추가된 원소를 먼저 반환하는 FIFO 구조였다면, 우선순위 큐는 큐 안의 원소를 특정한 우선순위에 따라서 정렬한 뒤 우선순위가 가장 높은 원소를 반환한다. 

priority queue vs heapq

파이썬에서도 우선순위 큐를 지원하는 모듈이 있다. 그러나 교재에서는 heapq 모듈을 사용해서 진행했다.

실제로 우선순위 큐를 구현할 때는 힙(heap)을 주로 사용하고, 파이썬의 우선순위 큐 구현 코드를 보면 heapq 모듈을 사용하고 있다고 하므로 기능의 차이는 없다. 

다만 priority queue 모듈은 thread-safe인 반면 heapq는 thread-safe가 아니다. thread-safe란 멀티 스레드 환경에서 각 스레드에서 사용하는 변수의 값이 다른 스레드에 의해 변경되지 않는 것을 의미한다. 

그럼 thread-safe를 지원하는 priority queue가 더 좋은 것이 아니야? 라고 생각할 수 있지만, thread-safe를 지원하기 위해서는 내부적으로 락킹(locking)을 지원해야 한다. 추가적인 기능을 제공하기 위해서 오버헤드가 발생할 수 있고, 코딩 테스트는 멀티 스레드(multi-thread) 환경에서 실행하지 않으므로 priority queue 모듈을 사용할 필요가 없는 것이다. 

Locking이란, 멀티 스레드 환경에서 여러 개의 스레드가 동시에 한 변수에 접근하는 것을 막는 것이다. 그래야만 한 스레드가 어떤 변수를 사용 중일 때 다른 스레드의 개입으로 해당 변수의 값이 바뀌지 않는다. 

heap

힙은 또 다른 자료형(ADT)이며 리스트나 연결 리스트 등 다양한 자료형으로 구현할 수 있지만 보통은 리스트로 구현하는 듯 하다. 

힙은 min heap과 max heap이 있고, min heap의 경우 부모 노드(parent)는 자식 노드(children)보다 작거나 같은 key 값을 갖는 게 특징이며, 이를 heap property라고 한다. 그 외에는 다른 자료구조처럼 노드를 추가나 삭제하는 것은 똑같다. 노드를 하나 삭제나 추가할 때마다 heap property를 위반하지 않도록 필요 시 부모 노드와 자식 노드의 값을 바꾸는 등의 정렬 작업을 한다. 

알고리즘

어쨋든 풀이에서는 힙 자료형을 사용하면 문제를 쉽게 풀 수 있다고 한다. 어떻게 가능할까?

힙에 heappush()로 여러 값을 넣으면 자동으로 정렬을 해 준다. 이후 heappop()로 가장 우선순위가 낮은(여기서는 값이 작은) 원소를 리턴할 수 있다. 

for i in range(len(lists)):
	heapq.heappush(lists[i].val)

다만 힙에서는 값이 연결 리스트의 노드 형식이 아니라 숫자 형식으로 되어 있으므로 연결 리스트 형식으로 바꿔주는 작업도 필요하다. 

새 연결 리스트 노드를 만든 뒤 next 포인터로 새로 만든 노드(ListNode(value))를 가리키게 하고, 포인터를 뒤로 한 칸씩 이동하면 된다. 

heap: key 중복

다만 heapq 라이브러리에서 구현한 힙은 중복 key 값을 허용하지 않는다. 문제의 예제에서는 값이 '1'로 중복되는 경우가 있어서 오류가 발생한다. 

이 경우 값을 가공하지 않은 채 숫자 형태로 넣지 말고, tuple 형태로 가공해서 0번째 인덱스에는 노드의 값을 넣고, 1번째 인덱스에는 해당 노드가 속한 연결 리스트가 input lists 중 몇 번째 인덱스인지를 입력해 주자. 그렇게 하면 설령 0번째 인덱스인 노드의 값이 서로 겹치더라도 그 다음 1번째 인덱스로 값을 구분해서 중복 오류가 나지 않는다. 물론 실제로 1번째 인덱스 값은 사용하지 않지만 말이다. 

heap: node.next

아까 for loop를 돌면서 lists의 i번째 인덱스를 넣었었다. 그런데 lists[i].val은 연결 리스트에 있는 모든 노드의 값이 아니라 연결 리스트의 첫 번째 노드의 값이다. 그래서 이 상태는 아직 그 다음 노드들의 값이 정렬되지 않은 상태이다. 

우선 각 연결 리스트의 첫 번째 노드들만 힙에 넣고, heappop()으로 가장 값이 작은 노드 하나를 리턴한다. 그리고 연결 리스트의 다음 노드를 다시 힙에 넣는다. 

맨 처음이 이런 상황이다. 현재 a 연결 리스트를 대상으로 정렬 작업을 하고 있다고 가정하면, 그 다음 상태는 이렇게 된다. 

이 방법이 가능한 이유는 각 연결 리스트(a, b, c)는 정렬이 된 상황이기 때문이다. 만약 그렇지 않았다면 모든 연결리스트의 모든 노드를 힙에 넣은 뒤 정렬을 해야 했을 것이다. 

참고한 포스트

https://docs.python.org/3/library/heapq.html

https://github.com/python/cpython/blob/main/Lib/heapq.py

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

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

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

* 해당 포스트는 641번 문제에 대한 정답 풀이를 포함하고 있지 않으며 공부하다 참고용으로 작성된 포스트입니다. *

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

데크는 큐의 일종이지만 큐와 달리 양쪽에서 원소를 조회, 삭제, 추가할 수 있다. 

데크 역시 큐와 스택처럼 ADT이며 연결 리스트, 이중 연결 리스트, 배열 등 다양한 자료형으로 구현할 수 있다. 

이번 문제는 그냥 데크가 아닌 원형 데크를 연결 리스트를 사용해서 구현하는 문제이다. 이전에 원형 큐를 구현하던 것처럼, 미리 고정된 크기의 공간을 할당한 뒤 포인터를 이동하는 방식으로 구현하면 된다. 

다만 데크는 맨 앞과 맨 뒤에서 모두 조회, 삽입, 삭제가 가능해야 하므로, 구현이 원형 큐보다 더 복잡하다. 

우선 삽입이나 삭제를 하기 전에는 데크의 상태(데크가 비어 있는지, 남은 공간이 있는지)를 확인해야 하므로 해당 메소드를 먼저 구현해 보자. 

1. isEmpty(), isFull()

이전에 풀었던 원형 큐 구현 문제에서처럼, front 포인터와 rear 포인터 두 개가 필요하다. front 포인터는 데크의 맨 앞의 원소를, rear 포인터는 데크의 맨 뒤 원소를 가리킨다. 

원소가 아예 없는 데크를 생각해 보면 front와 rear 포인터는 같은 곳을 가리키고 있을 것이다. 원소가 삽입되면 front 또는 rear 포인터가 이동하면서 둘 사이의 거리가 벌어질 것이다. 

하지만 front와 rear 포인터의 값이 같다고 데크가 비어 있지 않을 수 있다. 데크가 꽉 찬 경우도 고려해야 한다. 말 그래도 '원형' 데크이기 때문에, 데크가 꽉 차면 front와 rear 포인터가 돌아서 다시 만나게 된다. 

이를 구분하는 방법은 front나 rear가 가리키는 인덱스에 값이 들어있는지이다. 값이 들어 있다면 full이고, 값이 없다면 empty이다. 

2. insertFront(), insertLast()

데크에다가 원소를 넣을 때, 맨 앞에다 넣을 수도 있고 맨 뒤에다 넣을 수도 있다. 맨 앞에 넣는 경우 front 포인터가 움직이고, 뒤에 넣으면 rear 포인터가 움직인다. 

그런데 어떻게 움직일까?

원형 데크는 이미 한정된 공간이 할당되어 있다. 최대 k개의 인덱스가 있고, 값이 할당되지 않은 인덱스는 null 값을 가진다. 전체 k개의 인덱스 공간 중 데크로 사용되는 공간은 front와 rear 포인터로 구분한다. front 포인터와 rear 포인터 사이에 있는 공간이 전체 k개의 인덱스 공간(사용할 수 있는 최대 공간) 중 실제 데크에서 원소가 들어가있는 부분이다. 

그렇다면 front와 rear의 사이가 멀어지면(원형 데크이므로, 정확히는 front에서 뒤 방향으로 이동할 때 rear이 더 멀어지면) 데크에는 원소가 추가되는 것이고, 반대로 front와 rear가 가까워지면 데크에서 원소가 삭제된다고 볼 수 있다. 

즉 front이 앞으로 한 칸 이동하면 front와 rear의 거리가 멀어지므로 데크에 원소가 추가되었다고 볼 수 있다. (insertFront)

또한 rear이 뒤로 한 칸 이동해도 front와 rear의 거리가 멀어지므로 데크에 원소가 추가된 것이다. (insertLast)

3. deleteFront(), deleteLast()

위의 경우와 반대로 front이 뒤로 한 칸 이동한다면 front와 rear의 거리가 가까워진다. 그러므로 데크에서 원소가 삭제되었다고 볼 수 있다. 현재 front가 가리키던 원소에다가 null 값을 할당해준 뒤 front 포인터를 뒤로 한 칸 옮겨서 구현할 수 있다. 

rear을 앞으로 한 칸 이동시켜도 같은 결과가 나온다. 

다만 front은 맨 앞 원소를 가리키지만 rear은 맨 뒤의 원소의 다음 인덱스(데크가 full이나 empty 상태라면 front와 같은 인덱스, 아니라면 빈 공간을 가리킨다)를 가리키므로, rear을 앞으로 한 칸 이동시킨 뒤 해당 인덱스에 null 값을 할당하면 된다. 

4. getFront(), getLast()

데크에 추가나 삭제를 하지 않으므로 포인터가 이동하지는 않는다. 다만 두 메소드 모두 사용 전 데크가 비었는지를 확인해야 하겠다. 

getFront()의 경우 front 포인터가 가리키는 원소를, getLast()의 경우 rear 포인터보다 한 칸 앞 위치에 있는 원소를 리턴하면 된다. 

전체 코드는 다음과 같다. 

(교재를 참고하지 않고 코드를 작성하였습니다.)

class MyCircularDeque(object):

    def __init__(self, k):
        self.deque = [None] * k
        self.size = k
        self.front = 0
        self.rear = 0

    def insertFront(self, value):
        if self.isFull():
            return False
        self.front = (self.front - 1) % self.size
        self.deque[self.front] = value
        return True

        
    def insertLast(self, value):
        if self.isFull():
            return False
        self.deque[self.rear] = value
        self.rear = (self.rear + 1) % self.size
        return True
        
    def deleteFront(self):
        if self.isEmpty():
            return False
        self.deque[self.front] = None
        self.front = (self.front + 1) % self.size
        return True
        
    def deleteLast(self):
        if self.isEmpty():
            return False
        self.rear = (self.rear - 1) % self.size
        self.deque[self.rear] = None
        return True
        
    def getFront(self):
        if self.isEmpty():
            return -1
        return self.deque[self.front]
        
    def getRear(self):
        if self.isEmpty():
            return -1
        position = (self.rear - 1) % self.size
        return self.deque[position]
        
    def isEmpty(self):
        if self.front == self.rear and self.deque[self.front] is None:
            return True
        return False
        
    def isFull(self):
        if self.front ==  self.rear and self.deque[self.front] is not None:
            return True
        return False

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

leetcode 622번 ( https://leetcode.com/problems/design-circular-queue/ )

풀이방법 1. (오답노트)

(문제를 잘못 이해하고 풀었던 풀이다.)

코드는 다음과 같다. 

class MyCircularQueue(object):

    def __init__(self, k):
        self.size = k
        self.queue = []

    def enQueue(self, value):
        if len(self.queue) == self.size:
            return False
        
        self.queue.append(value)
        return True

    def deQueue(self):
        if len(self.queue) == 0:
            return False
        
        self.queue.remove(self.queue[0])
        return True
        
    def Front(self):
        if self.isEmpty():
            return -1
        return self.queue[0]
        
    def Rear(self):
        if self.isEmpty():
            return -1
        return self.queue[-1]
        
    def isEmpty(self):
        return len(self.queue) == 0
        
    def isFull(self):
        return len(self.queue) == self.size

원형 큐를 구현하고, 언어에서 기본으로 제공되는 큐(파이썬의 경우는 데크) 자료형을 사용하지만 않으면 되는 문제라고 생각했다. 그래서 큐를 빈 리스트 자료형으로 구현했었다. 

하지만 원형 큐(circular queue)의 중요한 장점 중 하나는 한정된 공간을 사용한다는 것이다. 빈 리스트[ ]를 사용해서 구현한다면 리스트에서 원소를 빼거나 추가하면서 메모리 상으로는 공간을 계속 추가해서 사용하게 된다. 

그러므로 원형 큐를 구현하려면 원형 큐를 매개변수 k를 받아서 초기화할 때, 미리 한정된 공간을 할당해 주어야 한다. 

풀이방법 2.

원형 큐를 초기화할 때 큐의 크기 k를 매개변수로 받는다. k로 원형 큐의 크기를 초기화하는 방법은 간단하다. 미리 리스트 배열의 크기대로 할당해 놓고 리스트의 크기를 추가(append)나 제거(pop)하는 메소드는 사용하지 않는 것이다. 

self.queue = [None] * k

원형 큐에는 사용할 큐 배열뿐만 아니라 다른 변수들도 필요하다. 

우선 배열의 최대값을 저장해 둬야 한다. 그래야 원소를 넣거나 뺄 때 배열의 최대값을 넘었는지 확인할 수 있다. 

(사실 배열의 최대값을 '넘었는지'를 확인하는 데에는 안 쓰이고, front 포인터와 rear 포인터 값을 이동시키는 데 쓰인다.)

def __init__(self, k):
        self.queue = [None] * k
        self.size = k	# max capacity
        self.front = 0	# pointer that points front element
        self.rear = 0	# pointer that points rear element

원형 큐처럼 정해진 크기의 공간이 할당되어 있고 2개의 포인터가 사용되는 자료구조를 구현한다면, 각 함수마다 각 포인터의 값을 어떻게 변화시킬지가 중요하다. 

front 포인터의 경우 맨 앞 원소의 인덱스를 가리키고, rear 포인터는 맨 뒤의 원소의 인덱스를 가리킨다. 그러므로 최대 k개의 인덱스가 있을 때, 실제로 값이 저장된 공간은 front 인덱스부터 rear 인덱스 사이 공간까지이다. 

dequeue()로 원소를 제거할 경우 먼저 제거할 원소가 있는지(큐가 비어있는지)를 확인한다. 

기존의 front 포인터가 가리키던 공간에다가는 null을 할당한 뒤 front 포인터를 한 칸 앞으로 증가시킨다. 

enqueue()로 원소를 추가할 경우 먼저 원소를 추가할 공간이 있는지(큐가 전부 차 있는지)를 확인한다. 

rear 포인터 자리에다가 새 원소를 추가하고, rear 포인터를 한 칸 이동시킨다. 

사실상 front 포인터는 실제 원소가 있는 인덱스를 가리키지만, rear 포인터는 맨 끝 원소의 인덱스 + 1을 가리키게 된다. 

다만 사용할 수 있는 공간은 맨 처음에 [None] * k로 총 k개의 인덱스만 할당해 두었기 때문에, 계속해서 front와 rear를 증가시키다 보면 금방 끝에 도달할 것이다. 만약 포인터가 k번째 인덱스를 찾으려고 한다면 값이 없어서 오류가 발생한다(0부터 k-1번째 인덱스까지만 있다). 

보통은 나눗셈 연산(modulo)을 사용해서 front와 rear 값이 계속 증가해도 0부터 k-1 범위 사이에만 존재하도록 처리할 수 있다. 어떤 수를 k로 나눌 경우 나머지는 무조건 0과 k-1 사이에 있기 때문이다. 

이를 참고해서 작성한 전체 코드이다.

(교재에서는 아이디어(인덱스가 k개인 초기화된 배열을 할당)만 참고하였고, 실제 코드는 교재를 참고하지 않고 작성하였다.)

class MyCircularQueue(object):

    def __init__(self, k):
        self.queue = [None] * k
        self.size = k
        self.front = 0
        self.rear = 0
        
    def enQueue(self, value):
        if self.isFull():
            return False
        
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.size
        return True
        
    def deQueue(self):
        if self.isEmpty():
            return False

        self.queue[self.front] = None
        self.front = (self.front + 1) % self.size
        return True
        
    def Front(self):
        if self.isEmpty():
            return -1
        return self.queue[self.front]
        
    def Rear(self):
        if self.isEmpty():
            return -1
        return self.queue[(self.rear)-1]
        
    def isEmpty(self):
        if self.front == self.rear and not self.queue[self.front]:
            return True
        return False
        
    def isFull(self):
        if self.front == self.rear and self.queue[self.front]:
            return True
        return False

참고한 포스트

https://docs.python.org/3/tutorial/datastructures.html