Today I learned
2022/01/18
회고록
1/18
항해 99, 알고리즘 1주차
교재 : 파이썬 알고리즘 인터뷰
9장 스택, 큐
1. 이론
- 파이썬과 큐(Queue)
서두에서 설명했지만 가장 먼저 입력 된 데이터가 가장 먼저 출력되는 구조이다. FIFO(First In, First Out)라고 부르기도 하며 반대로 LILO(Last In, Last Out)이라고 설명하기도 한다. 현실세계에서 식당에서 줄을 서는 경우를 큐의 예시로 들 수 있다. 먼저 줄을 선 순서대로 식당에 입장한다.
큐에서 알아두어야 할 용어가 있는데 Enqueue(인큐), Dequeue(디큐)이다.
-. Enqueue : 큐에서 데이터를 입력하는 기능
-. Dequeue : 큐에서 데이터를 꺼내는 기능
추가로 파이썬에서는 queue라는 내장 모듈을 제공한다. 아래 예시로 든 그림을 통해 코드를 작성해보았다. put( )은 큐에 데이터를 넣을 때 사용하는 메서드, get( )은 큐에서 데이터를 꺼내는 메서드이다
<코드>
import queue
#큐 모듈의 큐 클래스 객체 선언
data = queue.Queue()
print(type(data))
#선언 된 큐 객체에 3개 데이터 입력하기 : 2,5,8
data.put(2)
data.put(5)
data.put(8)
#큐 객체에서 입력된 객체 하나씩 꺼내기 :FIFO
print(data.get())
print(data.get())
print(data.get())<결과>
<class 'queue.Queue'>
2
5
8숫자 2,5,8을 순서대로 넣고 get( )을 3번 하면 먼저 입력 된 순서대로 출력된다.
queue 내장 모듈 내에는 기본적인 Queue( ) 클래스 외에도 LifoQueue( ), PriorityQueue( ) 클래스가 존재한다. 여기서 자세히 다루진 않겠지만 LifoQueue( )는 스택과 같은 LIFO 구조, PriorityQueue( ) 는 사용자가 우선순위를 지정한대로 데이터를 꺼낼 수 있는 구조라고 보면 될 것 같다.
- 파이썬과 스택(Stack)
스택은 나중에 입력 된 데이터가 먼저 출력되는 LIFO(Last In, First Out) 자료 구조이다. 반대로 FILO(First In, Last Out)라고 부르기도 한다. 예시로 들만한게 하노이의 탑 게임을 들 수 있다. 하노이의 탑 게임에서는 스택과 같이 원판을 무조건 위에서부터 빼야 한다(마지막에 들어간 원판부터). 중간에서 빼는건 불가능하다.
스택에서는 Push, Pop이라는 용어가 있다.
-. Push : 데이터를 입력하기
-. Pop : 데이터를 꺼내기(마지막으로 입력 된 순서부터)
위 그림을 파이썬으로 구현하려면 리스트를 선언해 append를 통해 데이터를 넣는다.(=Push)
꺼낼 때는 리스트의 pop( ) 함수를 사용하면 된다.
<코드>
#빈 리스트 선언
stack = []
#2,5,8 차례대로 리스트에 추가하기(=Push)
stack.append(2)
stack.append(5)
stack.append(8)
#값이 모두 입력된 리스트 출력하기
print("stack : ", stack)
#리스트 pop함수 통해 마지막으로 입력된 데이터 순 출력
print("첫번째 pop")
print(stack.pop())
print(stack)
print("두번째 pop")
print(stack.pop())
print(stack)
print("세번째 pop")
print(stack.pop())
print(stack)<결과>
stack : [2, 5, 8]
첫번째 pop
8
[2, 5]
두번째 pop
5
[2]
세번째 pop
2
[]위 결과를 보면 알겠지만 pop( ) 한번 실행할 때마다 리스트의 마지막 요소가 출력되고 없어지는 것을 확인할 수 있다.
2. 문제
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 10^5
30 <= temperatures[i] <= 100
https://leetcode.com/problems/daily-temperatures/
3. MySol
def solution(Temperatures):
result = [0]*len(Temperatures)
for i in range(0,len(Temperatures)-1):
for j in range(i,len(Temperatures)):
if Temperatures[i] < Temperatures[j]:
result[i]=j-i
break
return result
if __name__ == '__main__':
T = [73,74,75,71,69,72,76,73]
result = solution(T)
print('result : ' + str(result))
def dailyTemperatures(T):
ret = [0] * len(T)
stack = []
for i, temp in enumerate(T):
#순서대로 stack에 넣다가, 온도가 높을 때만 while문 돈다
if i!=0:
print('==================================== Day Temperature : ' + str(temp) + ', T[stack[-1]] : ' + str(T[stack[-1]]) + ', i : ' + str(i))
else :
print('==================================== Day Temperature : ' + str(temp) + ', i : ' + str(i))
while stack and T[stack[-1]] < temp:
#stack을 인덱스 리스트로 활용
print('stack[-1] : ' + str(stack[-1]) + ', T[stack[-1]] : ' + str(T[stack[-1]]) + ', temp : ' + str(temp))
print('before pop from stack : ' + str(stack))
#맨 뒤의 값을 뽑는다
index = stack.pop()
print('after pop from stack : ' + str(stack))
print('i - index : ' + str(i - index) + ', i : ' + str(i) + ', index : ' + str(index))
ret[index] = i - index
print('ret[] : ' + str(ret))
#i를 넣어준다
stack.append(i)
print('------------------------ push stack : ' + str(stack))
return ret
if __name__ == '__main__':
T = list([73,74,75,71,69,72,76,73])
result = dailyTemperatures(T)
print('result : ' + str(result))
4. 배운 점
- 반복문으로 해당 문제를 해결하려하니, 리트코드에서 시간초과로 통과가 되지 않았다.
- 반복문이 접근 및 해결은 직관적이고 쉬우나, 스택을 이용하여 구현하는 편이 시간 복잡도에 있어 더 효율적이다.
- 스택을 이용하여 스택에 해당 날짜의 온도를 넣었다가 더 높은 온도가 다가올때 빼주면, index값의 차이로 인하여 온도를 구할 수 있다. 이 부분을 이해하는 것이 핵심
5. 총평
스택 훈련
