스택, 큐
Question 20: Linked List Cycle
괄호로 된 입력값이 올바른지 판단하라 입력: (){}[]
출력: true
풀이 1: 스택 일치 여부 판별
class Solution:
def isValid(self, s: str) -> bool:
stack = []
table = {')':'(', ']':'[','}':'{'}
for char in s:
if char not in table:
stack.append(char)
elif not stack or table[char] != stack.pop():
return False
return len(stack) == 0
중요 내용
- stack 변수에 append 와 pop을 반복해나가는 알고리즘이다. 이렇게 리스트에 값을 추가하며 값을 제거해 나가는 알고리즘은 자주 쓰이는 방법이므로 꼭 숙지하도록 하자!
Question 21: 중복 문자 제거
중복된 문자를 제외하고 사전식 순서로 나열하라
입력: ‘cbacdcbc’
출력: ‘acdb’
사전식 순서는 다음과 같은 규칙이 있는 것을 발견하였다.
- 문자열을 앞에서부터 차례로 문자를 서로 비교한다.
- 문자가 문자열에서 한개 나타나면 해당 문자는 그대로 둔다.
- 문자가 문자열에서 여러개 나타나고 바로 뒤에 있는 문자보다 작으면 그대로 둔다.
풀이 1: 재귀를 이용한 분리
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
# 집합으로 정렬
for char in sorted(set(s)):
suffix = s[s.index(char):]
# 전체 집합과 접미사 집합이 일치할때 분리 진행
if set(s) == set(suffix):
return char + self.removeDuplicateLetters(suffix.replace(char, ''))
return ''
중요 내용
- 다음과 같은 순서로 재귀 구조가 실행된다.
- 문자열에서 중복된 문자를 제거하고 알파벳 순서로 정렬한다.
- 정렬한 문자 순서대로 반복문을 돈다.
- 접미사(suffix)는 iterator 로부터 슬라이싱한 값이다.
- set(문자열)=set(suffix) 이면 suffix를 분리하고 iterator를 공백으로 만든다.
- removeDuplicateLetters 함수에 suffix를 인수로 넣음으로써 1~4의 과정을 반복한다.
풀이 2: 스택을 이용한 문자 제거
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
counter, seen, stack = collections.Counter(s), set(), []
for char in s:
counter[char] -= 1
if char in stack:
continue
while stack and char < stack[-1] and counter[stack[-1]] > 0:
seen.remove(stack.pop())
stack.append(char)
seen.add(char)
return ''.join(stack)
기억해야 할 함수
- collections.Counter(string): 문자열에서 각 문자가 나온 횟수만큼을 딕셔너리로 만들어 리턴한다.
중요 내용
- 이 방법 또한 처음에는 이해하기 매우 어려웠으나 다음과 같은 규칙을 찾으니 이해하기 한결 수월해졌다.
- 문자가 s에 하나밖에 없는 경우에는 stack에 그대로 둔다.
- 만약 다음 iterator가 stack의 제일 마지막의 문자보다 작고 그 문자가 s에 한개 이상 존재하면 그 문자를 지우고 iterator를 append 한다. 이 때, 반복문은 while문을 씀으로써 iterator와 stack의 제일 마지막의 문자와 비교하는 것을 반복한다.
Question 22: 일일 온도
온도를 입력받은 후 더 따뜻한 날씨를 위해서 몇일을 기다려야 하는가?
입력: T = [73,74,75,71,69,72,76,73]
출력: [1,1,4,2,1,1,0,0]
내 풀이
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
for i,tmp in enumerate(temperatures):
for j,tmp2 in enumerate(temperatures[i+1:]):
if tmp2 > tmp:
stack.append(j+1)
break
if j==len(temperatures[i+1:])-1:
stack.append(0)
if i==(len(temperatures)-2):
break
stack.append(0)
return stack
- 브루트 포스 방법을 이용하여 깔끔하지 않은 방법으로 풀었다.
- 예외처리가 많이 필요한 방법이여서 좋은 방법은 아니다.
결과
타임에러가 떴다.
풀이 1: 스택 값 비교
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
days = [0] * len(temperatures)
for i,tmp in enumerate(temperatures):
while stack and tmp>temperatures[stack[-1]]:
last = stack.pop()
days[last] = i - last
stack.append(i)
return days
중요 내용
- days 변수에 temperatures의 요소의 갯수만큼 0을 사전에 부여한 후 반복문을 돌며 나중에 바꾸는 방법이다.
- 기존 풀이 방법과는 다르게 stack에 요소의 값이 아닌 인덱스 값을 저장하였다.
- stack, pop, while문을 이용하여 만들어낼 수 있는 알고리즘을 생각하자!
Question 23: 큐를 이용한 스택 구현
큐를 이용해 스택을 구현하라
입력: stack.push(1)
입력: stack.push(2)
입력: stack.pop()
출력: 2
내 풀이
파이썬의 큐에 대해 아는 것이 거의 없어서 결국 풀지 못하였다.
풀이 1: push() 할 때 큐를 이용해 재정렬
class MyStack:
def __init__(self):
self.q = collections.deque()
def push(self, x: int) -> None:
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft()
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return len(self.q) == 0
중요 내용
- 파이썬에서의 큐의 구현은 데크(deque)를 이용한다.
- 데크는 사용할 수 있는 함수가 append, popleft 이므로 이 두개의 함수를 이용해 스택을 구현해야 한다.
Question 24: 스택을 이용한 큐 구현
스택을 이용해 큐를 구현하라
입력: stack.push(1)
입력: stack.push(2)
입력: stack.pop()
출력: 1
내 풀이
결국 풀지 못하였다.
풀이 1: 스택 2개 사용
class MyQueue:
def __init__(self):
self.stack = []
self.q = []
def push(self, x: int) -> None:
self.stack.append(x)
def pop(self) -> int:
self.peek()
return self.q.pop()
def peek(self) -> int:
if not self.q:
while self.stack:
self.q.append(self.stack.pop())
return self.q[-1]
def empty(self) -> bool:
return (len(self.stack) + len(self.q)) == 0
중요 내용
- 큐를 이용해 스택을 구현할 때의 풀이와는 다르게 pop과 append를 한번에 같이 사용하면 삭제했다가 추가하는 과정을 무한 반복하기 때문에 이 방법은 사용할 수 없다.
- 클래스 안의 함수에서 같은 클래스 안의 다른 함수를 구현할 때 다른 함수의 return 문은 값을 반환하는데 사용된다.
Question 25: 원형 큐 디자인 (재풀이)
원형 큐를 디자인하라
입력:
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(3);
myCircularQueue.enQueue(4);
myCircularQueue.Rear();
myCircularQueue.isFull();
myCircularQueue.deQueue();
myCircularQueue.isEmpty();
출력: True
True
4
False
True
False
내 풀이
class MyCircularQueue:
def __init__(self, k: int):
self.q = []
self.k = k
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
else:
self.q.append(value)
return True
def deQueue(self) -> bool:
if self.isEmpty():
return -False
else:
self.q.pop(0)
return True
def Front(self) -> int:
if self.isEmpty():
return -1
else:
return self.q[0]
def Rear(self) -> int:
if self.isEmpty():
return -1
else:
return self.q[-1]
def isEmpty(self) -> bool:
return len(self.q) == 0
def isFull(self) -> bool:
return len(self.q) == self.k
결과
Runtime: 85 ms, faster than 50.03% of Python3 online submissions for Design Circular Queue. Memory Usage: 14.5 MB, less than 96.23% of Python3 online submissions for Design Circular Queue
- 이 문제는 난이도가 별 두개인 것이 이해가 되지 않을 정도로 쉽게 풀었다.
- 큐의 모양이 원형이라는 특징을 살리지 않은 풀이 방법이여서 다소 변칙적인 풀이 방법이라고 할 수 있다.
풀이 1: 값만 변경
class MyCircularQueue:
def __init__(self, k: int):
self.q = [None] * k
self.maxlen = k
self.p1 = 0
self.p2 = 0
# enQueue(): 리어 포인터 이동
def enQueue(self, value: int) -> bool:
if self.q[self.p2] is None:
self.q[self.p2] = value
self.p2 = (self.p2 + 1) % self.maxlen
return True
else:
return False
# deQueue(): 프론트 포인터 이동
def deQueue(self) -> bool:
if self.q[self.p1] is None:
return False
else:
self.q[self.p1] = None
self.p1 = (self.p1 + 1) % self.maxlen
return True
def Front(self) -> int:
return -1 if self.q[self.p1] is None else self.q[self.p1]
def Rear(self) -> int:
return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]
def isEmpty(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is None
def isFull(self) -> bool:
return self.p1 == self.p2 and self.q[self.p1] is not None
기억해야 할 함수
- 표현식 if 가정문 else 표현식: if, else문을 한 줄로 풀어서 쓸 수 있다.
중요 내용
- 투 포인터 방법을 이용한 풀이 방법이다. front는 제일 앞의 값에 위치한 포인터이고, rear은 제일 뒤에 위치한 포인터이다.
- 값을 추가하면 rear 포인터가 추가한 값으로 이동하고 값을 삭제하면 front 포인터가 삭제한 값 다음으로 넘어간다.
Comments