문제 1. 일일온도
문제설명
-
매일의 화씨 온도 리스트 T를 입력받아서, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야하는지를 출력하라.
-
ex) 입력 T = [73,74,75,71,69,72,76,73] -> 출력: [1,1,4,2,1,1,0,0]
스택을 이용한 풀이
def dailyTemp(T):
answer = [0] * len(T)
stack = []
for i, cur in enumerate(T):
# 현재 온도가 스택 값보다 높다면 현재 인덱스 - stack 인덱스
while stack and cur > T[stack[-1]]:
last = stack.pop()
answer[last] = i - last
stack.append(i)
return answer- 현재의 인덱스를 계속 스택에 쌓고, 이전보다 상승하는 지점이 나타난다면 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교해서 더 높다면 기존 스택의 값은 팝으로 꺼내고 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다.
- while stack : 은 stack 리스트 안에 값이 하나라도 있을 경우 참이 된다.
문제 2. 큐를 이용한 스택 구현
큐
- 큐는 FIFO(선입선출) 로 처리되는 상대적으로 스택에 비해서는 쓰임새가 적은 자료구조이다. 하지만 데크나, 우선순위 큐, 너비 우선 탐색(BFS) 등 널리 쓰인다.
- 파이썬의 리스트는 큐의 모든 연산을 지원한다.
- 데크는 좀 더 나은 성능을 가지고, 양방향 삽입 삭제가 모두 가능하다.
문제 설명
큐를 이용해 다음 연산을 지원하는 스택을 구현하라.
- push(x) : 요소 x를 스택에 삽입한다.
- pop() : 스택의 첫 번째 요소를 삭제한다.
- top() : 스택의 첫 번째 요소를 가져온다.
- empty(): 스택이 비어 있는지 여부를 리턴한다.
풀이
class MyStack:
def __init__(self):
self.q = collections.deque()
def push(self,x):
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):
return self.q[0]
def empty(self):
return len(selq.q) == 0- push의 경우를 제외하면 간단한 코드이다.
- push는 맨 뒤에 요소를 삽입 후 , 삽입한 값을 맨 앞으로 두기 위해서 삽입한 값을 제외한 모든 값을 popleft()를 통해서 맨 뒤로 한 개씩 붙이는 작업을 추가한다.
문제 3. 스택을 이용한 큐 구현
문제 설명
스택을 이용해 다음 연산을 지원하는 큐를 구현하라.
- push(x) : 요소 x를 큐 마지막에 삽입한다.
- pop() : 큐의 첫 번째 요소를 제거한다.
- peek() : 큐의 첫 번째 요소를 조회한다.
- empty(): 큐가 비어 있는지 여부를 리턴한다.
스택 2개 사용하여 풀이
class MyQueue:
def __init__(self):
self.input = []
self.output = []
def push(self,x):
self.input.append(x)
def pop(self):
self.peek()
return self.output.pop()
def peek(self):
#output이 없으면 모두 재입력
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 == []- peek과 pop은 같은 데이터를 불러오기 때문에, pop을 구현할 때 peek을 통해 데이터를 불러오고 pop으로 제거하는 알고리즘이다.
- peek의 경우에는 output 리스트가 비어있으면 input리스트에 있는 값들을 전부 역순으로 output에 입력하고, output 리스트의 마지막 값을 리턴한다. ( 즉, input 값의 첫번째 값을 return 한다. )
문제 4. 원형 큐 디자인
문제 설명
원형 큐를 디자인하라.
- 원형 큐는 FIFO 구조를 지닌다는 점에서 기존의 큐와 동일하다. 그러나 마지막 위치가 시작 위치와 연결되는 원형 구조를 가진다.
- 링 버퍼(Ring Buffer) 라고도 한다.
- 동작하는 원리는 투 포인터와 비슷하다. 기존의 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없지만, 원형 큐는 앞쪽에 공간이 남아있다면 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용이 가능한 구조이다.
풀이
class MyCircularQueue:
def __init__(self,k):
self.q = [None] * k
self.p1 = 0
self.p2 = 0
# enQueue(): rear포인터 이동
def enQueue(self, value) :
if selq.q[self.p2] is None:
self.q[self.p2] = value
self.p2 = (self.p2 + 1) % self.maxlen
return True
else:
return False
# deQueue(): front 포인터 이동
def deQueue(self):
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):
return -1 if self.q[self.p1] is None else self.q[self.p1]
def Rear(self):
return -1 if self.q[self.p2 - 1 ] is None else self.q[self.p2 - 1]
def isEmpty(self):
return self.p1 == self.p2 and self.q[self.p1] is None
def isFull(self):
return self.p1 == self.p2 and self.q[self.p1] is not None- 초기화시 큐의 크기k를 입력받고, 최대 길이인 maxlen으로 지정한다. p1 은 front의 포인터, p2는 rear의 포인터로 초기값은 0으로 지정했다.
- enQueue를 통해 rear 포인터를 이동시킨다. 해당 포인터가 가리키는 지점의 값이 None이면 value를 넣고 포인터를 앞으로 이동한다. ( maxlen 의 값을 넘는 걸 방지하기 위해 maxlen의 나머지 값으로 포인터 값일 지정해준다. 그리고 비정상적인 경우에는 False 를 리턴한다.
- deQueue의 경우에는 enQueue와는 같은 방식이지만 넣는 값을 반대로 진행하면 된다. ( front 포인터를 움직여 값을 비우는 작업이기 때문이다.)
- Front() , Rear() 연산은 해당 포인터 지점의 값을 가져오는 연산이다. 그러므로, Front()는 첫 번째 요소를 조회하는 연산이다.
- isEmpty() 와 isFull() 은 큐가 비었는지, 혹은 가득 채워져 있는지 조회하는 연산이다.
Univ of Seoul , Statistics