[스택이란?]
한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조. [컴퓨터인터넷IT용어대사전]
LIFO(Last In First Out)
이런 자료구조가 왜 필요한가?
넣은 순서를 쌓아두고 있기 때문
그 순서가 필요한 경우가 있음
ex) 되돌리기(Ctrl + Z)
[스택의 기능]
push(data) : 맨 앞에 데이터 넣기
pop() : 맨 앞의 데이터 뽑기
peek() : 맨 앞의 데이터 보기
isEmpty() : 스택이 비었는지 안 비었는지 여부 반환해주기
스택은 데이터 넣고 뽑는 걸 자주하는 자료 구조!
링크드 리스트와 유사하게 구현할 수 있음!!
[push 함수]
stack = [4]
스택에 3을 push 하면
[3] → [4] 가 되어야 함
링크드 리스트에서 새로운 head를 지정하려면
새로운 값을 담은 새로운 노드를 만들고
그 노드의 다음 노드를 현재의 head 로 지정하고
그 노드를 head 로 정하면 됨
def push(self, value):
new_node = Node(value)
new_node.next = self.head
self.head = new_node
[pop 함수]
stack = [3] → [4]
스택에 pop을 하면
[4] 가 되어야 함
링크드 리스트에서 head 를 제거하려면
현재 head 의 값을 다른 변수에 저장해 둔 다음
head 가 지칭하는 노드를 현재 head 의 다음값으로 지정
그리고 아까 저장해둔 head 를 반환
def pop(self):
if self.is_empty():
return "stack is empty"
delete_head = self.head
self.head = self.head.next
return delete_head
[peek 함수]
head 를 반환
def peek(self):
if self.is_empty():
return "stack is empty"
return self.head.data
[is_empty 함수]
head 가 None 인지 아닌지 여부를 반환
def is_empty(self):
return self.head is None
[문제]
수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한 ,한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.
예를 들어 높이가 6, 9, 5, 7, 4 인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고 받습니다.
높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑에서 수신하고,
높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이,
높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다.
높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.
이 때, 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 반환하시오.
[6, 9, 5, 7, 4] # 라고 입력된다면
<- <- <- <- <- 레이저의 방향
I
I
I I
I I I
I I I I
I I I I I
I I I I I
I I I I I
I I I I I
[0, 0, 2, 2, 4] # 다음과 같이 반환
풀이)
자신의 위치보다 왼쪽에 있는 탑들을 하나 하나 보면서
자기보다 크다면 그 위치를 설정
탑의 높이가 담긴 배열들을 stack 이라고 한다면
맨위의 값부터 하나하나 pop 하면서 원소들과 비교하는 방법
top_heights = [6, 9, 5, 7, 4]
def get_receiver_top_orders(heights):
array = [0] * len(heights)
while heights: # heights가 있는 동안 반복
height = heights.pop()
for idx in range(len(heights)-1, 0, -1):
if heights[idx] > height:
array[len(heights)] = idx + 1
break
return array
print(get_receiver_top_orders(top_heights)) # [0, 0, 2, 2, 4][시간복잡도]
heights 의 길이만큼 while 문을 쓰는데
내부에 for 문이 len(heights) 만큼 도니까
O(N^2) 겠구나 생각