아스

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

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

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

leetcode 232번 ( https://leetcode.com/problems/implement-queue-using-stacks/ )

풀이방법 1. 

교재를 보지 않고 시도했던 방법이다. 이전 문제와 비슷하게, 스택에서 사용할 수 있는 메소드만 사용해서 큐를 구현하는 문제이다. 

이전의 큐는 원소를 빼낼 때는 앞에서, 원소를 넣을 때는 뒤에서 넣었다(FIFO). 반면 스택은 원소를 넣는 것과 빼는 작업이 모두 맨 뒤에서 일어난다(LIFO). 그래서 스택을 큐로 구현할 때처럼 큐의 앞에서 원소를 뺀 다음에 큐의 맨 뒤에 넣는 방식으로, 공간을 안 사용하고 풀 수는 없다. 스택에서 원소를 하나 빼서 하나를 다시 넣는다고 해서 스택의 값이 변하지 않기 때문이다. 

그래서 스택 하나를 더 사용해서 정렬 작업을 할 것이다. 

(여기서는 스택을 모두 리스트로 구현하였다.)

이제 push(), pop(), peek() 메소드를 구현해야 하는데, 어디서 정렬하는지는 상관없다. 이번 풀이에서는 push()할 때 정렬을 같이 진행했다. 

기존 스택을 stack, 순서를 바꾸는 데 필요한 새 스택을 reverse로 두었다.

1. 새 값이 들어오면 먼저 기존 stacl에 있던 원소들을 전부 reverse로 옮긴다.

2. 빈 스택에 새 값을 먼저 넣은 뒤, reverse에 있던 값들을 다시 stack으로 옮기면 된다. 

하노이 탑과 비슷한 원리이다. 

push()에서 정렬 작업을 모두 마쳤기 때문에 pop(), peek() 메소드는 간단하게 구현할 수 있다. 

peek()은 stack의 맨 마지막 원소를 리턴하면 되므로, 우선 원소가 있는지를 확인한 뒤 -1번째 인덱스를 리턴하면 된다. 

(비어 있는 리스트에서 인덱스를 참조할 경우 오류가 나므로 주의하자)

pop()의 경우, 리스트에서 기본으로 제공되는 메소드이므로 그냥 사용하면 된다. 

peek()과 마찬가지로 원소가 없는 리스트에서 pop()을 할 경우 오류가 발생하므로 길이를 확인한 뒤 실행하자. 

전체 코드는 다음과 같다. 

class MyQueue(object):

    def __init__(self):
        self.stack = []
        self.reverse = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        for _ in range(len(self.stack)):
            self.reverse.append(self.stack.pop())
        
        self.stack.append(x)
        for _ in range(len(self.reverse)):
            self.stack.append(self.reverse.pop())

        

    def pop(self):
        """
        :rtype: int
        """
        if len(self.stack) >= 1:
            return self.stack.pop()
        

    def peek(self):
        """
        :rtype: int
        """
        if len(self.stack) >= 1:
            return self.stack[-1]
        

    def empty(self):
        """
        :rtype: bool
        """
        return len(self.stack) == 0

풀이방법 2. 

교재에서 언급된 풀이방법이다. 두 개의 스택(리스트로 구현)을 사용한다는 점은 같은데, 시공간 복잡도가 더 효율적이다. 

이전 방법에서는 push()를 시행할 때마다 정렬을 진행하였는데, 이 경우 매번 stack에 있던 원소를 reverse로 옮긴 뒤, 새 원소를 넣고, 다시 reverse에서 stack으로 옮기면서 시간이 더 소요될 수 있다. 

여기서도 두 개의 스택을 사용하지만 각 스택을 그때그때 들어오는 원소를 담아두는 input, peek()나 pop()이 호출될 때 스택을 정렬하기 위한 output으로 구분하였다. 

즉 push()가 호출될 때마다 매번 정렬이 일어나지 않고, 정렬이 일어나더라도 모든 원소를 옮기지 않는 방식이다. 

peek()나 pop()이 호출되면 우선 output 스택에 원소가 있는지 확인한다. 만약 원소가 있다면, 이 원소들은 input 스택에 들어있는 원소보다 이전에 들어온 원소들이 이미 정렬된 상태이므로, 여기서 가장 위에 있는 것을 제거한다. 

만약 output 스택에 원소가 없다면, 그 때는 input 스택에 있던 원소를 output 스택으로 옮긴다. 이전 풀이에서의 하노이 탑과 같은 원리이기 때문에 input에서 가장 먼저 들어왔던 원소가 output 스택의 맨 위에 오게 된다. 

이후 또 peek()나 pop()이 호출된다면, 그 때는 input 스택에 원소가 있던 없던 상관없이 output 스택의 맨 위에 가장 먼저 들어온 원소가 있으므로, output 스택이 빌 때까지 차례대로 빼서 사용하면 된다. 

같은 원리이지만 불필요한 정렬을 줄인 방법이라고 볼 수 있겠다. 

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

leetcode 225번 ( https://leetcode.com/problems/implement-stack-using-queues/description/ )

풀이방법.

보통 큐나 스택은 배열이나 연결 리스트(linked-list)로 많이 구현하는데, 이 문제는 특이하게 스택을 큐로 구현하는 문제였다. 큐와 스택은 배열이나 연결 리스트처럼 실제로 구현된 자료구조 형태가 아닌 추상적인 자료구조(ADT, abstract data types)이다. 그래서 실제 사용할 때는 다른 자료구조를 이용하여 구현한다. 

파이썬에는 스택의 push()와 pop(), 큐의 enqueue(), dequeue() 메소드가 모두 구현된 데크(deque) 자료형이 있다. 그러나 이 문제에서는 큐 ADT에서만 사용할 수 있는 메소드(enqueue, dequeue)만 가지고 스택을 구현해야 한다. 

데크에서는 popleft(), append()가 각각 enqueue(), dequeue()와 같은 기능을 한다.

스택과 큐는 원소를 추가할 때는 리턴되는 값이 없고 원소를 빼낼 때 값을 리턴하는데, 리턴하는 값의 순서가 다르다. 그러므로 원소를 넣을 때나 뺄 때 추가로 정렬 작업이 필요하다. 

여기서는 원소를 넣을 때 정렬 작업을 해 주었다. 

class Stack:
	
	def __init__(self):
		self.queue = collections.deque()
        
	def push(self, val):
		self.queue.append(val)
		self.queue.append(self.queue.popleft())
            
	def pop(self):
		return self.queue.popleft()
        
	def peek(self):
		return self.queue[0]
        
	def empty(self):
		return len(self.queue) == 0

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

leetcode 739번 ( https://leetcode.com/problems/daily-temperatures/description/ )

풀이 방법 1. 

스택을 사용한다. 

결과로는 각 i번째 날 이후로 따뜻해지기 위해 기다려야 하는 일 수를 리턴해야 하므로, 스택 및 결과에는 인덱스 정보를 저장하는 것이 좋겠다. 

우선 큰 틀에서 for loop를 사용해서 temperatures의 전체 요소를 순회할 수 있도록 한다. 

각 시행의 값(i번째 날의 인덱스와 온도)을 가지고, 우선 스택에 값이 있는지를 확인한다. 

파이썬에서는 for문으로 리스트의 인덱스와 값을 동시에 순회하고 싶을 때 enumerate()를 사용할 수 있다. 

for index, temperature in enumerate(temperatures):
	# index: index
	# temperature: value

이후 스택의 가장 위에 있는 값보다 i번째 날의 온도가 더 높으면, while 문을 사용해서 하나씩 스택에서 제거한다. 

while stack and temperature > temperatures[stack[-1]]:
	# pop index of day from stack
	# assign value of index to answer list

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

leetcode 316번 ( https://leetcode.com/problems/remove-duplicate-letters/description/ )

풀이방법 1. 

재귀함수를 이용할 수 있다. 

중복 문자를 제거해서 알파벳 순서(lexicographical order)가 가장 빠르려면, 알파벳에서 앞에 오는 문자는 앞에, 뒤에 오는 문자는 뒤에 있어야 한다(당연). 

set() 함수를 사용하면 문자열이나 리스트의 원소들 중 중복을 제거해서 지정된 순서 없이 리턴한다. 

이후 sorted() 함수를 리스트에 사용하면 리스트의 원소들을 알파벳 순서에 맞게 정렬할 수 있다. 

for char in set(sorted(s)):

해당 풀이에서는 조건에 맞는 문자열을 하나씩 뒤에다가 붙여서 결과값을 리턴하는 방식으로 진행한다. 

즉 i번째 단계에서 계산 중인 정답 문자열에다가 새 문자열을 이어 붙인다고 해 보자. 

이어 붙이려는 문자열은 자신의 앞에만 포함되어 있는 다른 문자열이 있으면 안 된다. 

예를 들어 acbefjgk 라는 문자열에서 a 다음에 b라는 문자열을 이어 붙일 수는 없다. 왜냐하면 a와 b 사이에는 c라는 문자열이 있고, c는 b 다음에는 한 번도 등장하지 않으므로 반드시 a와 b 사이에 등장해야 하기 때문이다. 

이를 확인하려면 문자열 char의 앞에 있는 문자열이 문자열 char의 뒤에도 등장하는지를 확인해야 한다. 

index() 함수를 사용해서 전체 문자열 중 char이 등장하는 첫 번째 인덱스를 알아낼 수 있다. 

이후 문자열 슬라이싱을 사용해서 해당 인덱스 이후의 문자열을 따로 슬라이싱한 뒤, set()을 사용하면 중복에 상관 없이 어떤 문자열이 등장하는지를 알 수 있다. 

suffix = s[s.index(char):]	# suffix of char
if set(s) == set(suffix):	
	# do something
	return thisfunction(strs.replace(char, "")

만약 문자열 char의 앞에 있는 모든 문자열이 문자열 char의 뒤에도 등장한다면, 어차피 for loop는 알파벳의 정렬된 순서대로 진행되므로 해당 문자열 char을 정답 문자열에 추가할 수 있다. 

다만 문자열 char이 정답 문자열에 포함되었으므로, 재귀함수를 사용해서 계산될 파라미터 문자열에서는 char 문자열을 모두 공백으로 바꿔 주어야 하겠다. replace() 함수로 간단하게 처리할 수 있다. 

string.replace(대체될 문자열 A, 대체할 문자열 B) : string 안에 있는 문자열 A를 문자열 B로 바꾼다. 

풀이방법 2.

스택을 이용해서 풀 수 있다. 

기본적으로는 주어지는 문자열들을 스택에 쌓다가, 특정 조건에 해당하면 스택의 문자열들을 제거한다. 재귀함수와 방식은 유사하고 사용하는 자료형이 다르다고 볼 수 있다. 

이외에도 Counter 자료형을 이용해서, 주어진 문자열에 각 문자가 몇 번 등장하는지를 기록 후 사용한다. 

counter = collections.Counter(s)

또한 set 자료형을 사용해서, 이미 계산을 마친 문자열은 해당 집합에 추가해서 이후 같은 문자열이 나올 경우 계산하지 않고 다음 loop로 넘어간다(continue). 

스택의 문자열을 제거하는 필수 조건도 앞의 재귀 함수와 비슷하다. 

스택에 문자열이 남아 있고, 새로 추가되는 문자열이 스택의 맨 위 문자열보다 알파벳 순서가 빠르고, 스택의 맨 위 문자열이 이 이후에도 등장한다는 조건이 충족되면, 스택과 set에서 문자열을 제거한다. 

while stack and stack[-1] > char and counter[stack[-1]] > 0:
	sets.remove(stack.pop())

최종적으로 스택에 남은 문자열이 정답이 된다. 

리스트 자료형을 문자열로 변경하기 위해서 공백 문자열을 기준으로 join() 메소드를 사용하면 간단히 바꿀 수 있다. 

return "".join(stack)

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

leetcode 20번 ( https://leetcode.com/problems/valid-parentheses/description/ )

풀이방법 1. 

스택을 이용해서 풀이한다. 

파이썬에는 별도의 스택이나 큐 자료구조가 없다. 리스트 자료형으로도 스택의 push()와 pop(), 큐의 enqueue(), dequeue() 메소드를 사용할 수 있다. 

다만 리스트는 포인터가 1개라서 리스트의 맨 앞에서 원소를 제거하는 데는 O(n)이 걸리므로, 성능을 생각한다면 collections 라이브러리의 deque 자료형을 쓰는 것이 더 빠르다. 

괄호는 여는 문자 (, [, { 와 닫는 문자 ), ], } 로 이루어져 있다. 

여는 문자가 나오면 스택에 넣는다. 닫는 문자가 나오면 스택의 맨 위의 여는 문자와 비교한 뒤, 일치하는 쌍이면 맨 위에서부터 괄호를 제거하고, 일치하지 않으면 False를 리턴하면 된다. 

또는 문자열이 아직 남아 있는데 스택이 빌 경우도 False를 리턴한다. 

마지막에 모든 문자열에 대해서 비교작업을 한 뒤, 스택이 비어 있는 경우에만 True를 리턴한다. 

스택은 저번처럼 좌우가 똑같은 문자열(팰린드롬)을 비교하는 등의 좌우대칭 문제뿐만 아니라, 괄호 등의 쌍을 비교하는 문제에서도 사용된다. 비슷한 유형이 나온다면 스택을 고려해 보자.