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을 하므로써 해당경우에 대한 예외처리를 한다.
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)
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
📝 주식가격 문제와 같은 풀이
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
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 == []
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