[3부 선형 자료구조] 9장 스택, 큐

📌 20) 유효한 괄호 ( 리트코드 20. Valid Parentheses )

✔ 풀이

class Solution(object):
    def isValid(self, s):
        table = {')': '(', ']': '[', '}': '{'}
        stack = []
        
        for c in s:
            if c not in table:
                stack.append(c)
            #stack이 비어있거나 짝이 안맞을경우
            elif not stack or stack.pop() != table[c]:
                return False
        return len(stack) == 0  #input = '[' 인경우 예외처리

📝 input = '['인 경우 for문 전체를 반복하고 통과한다. return len(stack) == 0을 하므로써 해당경우에 대한 예외처리를 한다.

📌 21) 중복 문자 제거 ( 리트코드 316. Remove Duplicate Letters )

✔ 풀이 (재귀 이용)

class Solution(object):
    def removeDuplicateLetters(self, s):
        #s중 사전순으로 가장 먼저 있는 알파벳부터 시작
        for c in sorted(set(s)):
            suffix = s[s.index(c):]  #현재 알파벳부터 끝까지 = 접미어
            #현재 알파벳부터 끝까지의 문자열이 가지고 있는 알파벳과 전체s가 가지고 있는 알파벳이 같음
            #=> 현재 위치 앞의 알파벳들은 중복이고, 제거한다.
            if set(s) == set(suffix):
                #접미어에 현재 알파벳을 제거하고 매개변수로 전달 (중복제거 위해)
                return c + self.removeDuplicateLetters(suffix.replace(c,''))
        
        return ''
    #그냥 return하면 None이 반환되어 + 연산 수행하지 못함
    #=> Typeerror 발생!

📝 +연산은 같은 type끼리 해야함 / 그냥 return은 None을 반환

✔ 풀이 (스택 이용)

from collections import Counter
class Solution(object):
    def removeDuplicateLetters(self, s):
        counter, stack, s_set = Counter(s), [], set()
        for c in s:
            counter[c] -= 1
            
            if c in s_set: #이미 처리한 알파벳은 넘어감
                continue
                
            #현재 알파벳이 stack[-1]보다 먼저오고 stack[-1]의 개수가 남아있을 경우
            while stack and c < stack[-1] and counter[stack[-1]] > 0:
                s_set.remove(stack.pop())  #다시 처리해야할 알파벳이 됨 / 스택에서 제거
            stack.append(c)
            s_set.add(c)
        
        return ''.join(stack)

📌 22) 일일 온도 ( 리트코드 739. Daily Temperatures)

✔ 풀이 (스택 이용)

class Solution(object):
    def dailyTemperatures(self, temperatures):
        answer = [0]*len(temperatures)
        
        stack = []
        for i, temp in enumerate(temperatures):
            #현재온도보다 낮은 온도가 stack에 없을때까지 
            while stack and temperatures[stack[-1]] < temp:
                last = stack.pop()
                answer[last] = i - last  #일수 차이 (=인덱스 차이)
            stack.append(i)
        
        return answer

📝 주식가격 문제와 같은 풀이

📌 23) 큐를 이용한 스택 구현 ( 리트코드 225. Implement Stack using Queues )

✔ 풀이

from collections import deque
class MyStack(object):

    def __init__(self):
        self.q = deque()

    def push(self, x):
        #가장 최근에 넣은 데이터가 가장 앞에 있을 수 있도록(큐에서 가장 먼저 pop될 수 있도록) 위치시킴
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()
        

    def top(self):
        #스택에서 top은 가장 최근에 넣은 데이터 = pop하면 나올 수 있도록 0에 위치시킴
        return self.q[0]  
        

    def empty(self):
        return len(self.q) == 0

📌 24) 스택을 이용한 큐 구현 ( 리트코드 232. Implement Queue using Stacks )

✔ 풀이

class MyQueue(object):

    def __init__(self):
        self.input = []
        self.output = []

    def push(self, x):
        self.input.append(x)
        
    def pop(self):
        self.peek()
        return self.output.pop()
        
    #output의 가장 마지막 인덱스에 pop할 데이터 위치시킴
    #output이 비어있다면 다시 갱신
    def peek(self):
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]
        
    def empty(self):
        return self.input == [] and self.output == []

📌 25) 원형 큐 디자인 ( 리트코드 622. Design Circular Queue )

✔ 풀이

class MyCircularQueue(object):

    def __init__(self, k):
        self.maxlen = k
        self.q = [None] * k
        self.p1 = 0  #맨 앞 요소 가르키는 포인터
        self.p2 = 0  #맨 뒤 요소 그 다음 가르키는
        

    def enQueue(self, value): #추가 연산은 p2가 이동
        if self.q[self.p2] == None:
            self.q[self.p2] = value #값 추가
            self.p2 = (self.p2 + 1) % self.maxlen #p2를 다음으로 이동 
            # 포인터 % maxlen 하는 이유 => 마지막 다음은 0 인덱스로 돌아와야하기 때문
            return True
        else: #가득 차 있어 추가 불가능함
            False
        
    def deQueue(self): #삭제 연산은 p1이 이동
        if self.q[self.p1] == None: #비어있으므로 삭제 불가
            return False
        else:
            self.q[self.p1] = None #삭제
            self.p1 = (self.p1 + 1) % self.maxlen
            return True

    def Front(self): #가장 맨 앞 요소 return
        #큐가 비어있을 경우 -1 return
        return -1 if self.q[self.p1] == None else self.q[self.p1]
        

    def Rear(self):  #가장 마지막 요소 return
        #큐가 비어있을 경우 -1 return
        return -1 if self.q[self.p2 - 1] == None else self.q[self.p2 - 1]
        #q는 파이썬의 리스트로 구성되어 있음 
        #=>마지막 값을 -1인덱스로 표현 
        #=> q[p2 - 1]는 항상 p2가 가르키는 위치의 전 값 가르킴
        #ex) p2 = 0일 때, 전 값의 위치는 4(마지막 인덱스) / 0 - 1 = -1(마지막 인덱스)
    
    def isEmpty(self):
        if self.p1 == self.p2 and self.q[self.p1] == None:
            return True
        else:
            return False
        

    def isFull(self):
        if self.p1 == self.p2 and self.q[self.p1] != None:
            return True
        else:
            return False