알고리즘 3주차 - 스택

스택

• 한쪽 끝으로만 자료를 놓고 뺄 수 있는 자료구조

• Last in First out, First in Last out(빨래통 구조)

• 넣은 순서를 쌓아두고 있기에 예를 들면 컴퓨터의 되돌리기 기능에 활용되는 구조

💡

스택이 제공하는 기능 push(data): 맨 위에 데이터 넣기 pop(): 맨 위의 데이터 뽑기 peek(): 맨 위의 데이터 보기 isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기 데이터의 삭제와 삽입이 잦은 자료 구조기에 링크드 리스트와 유사하게 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Stack:
    def __init__(self):
        self.head = None

    def push(self, value):
        new_head = Node(value)
        new_head.next = self.head
        self.head = new_head

    # pop 기능 구현
    def pop(self):
        if self.is_empty():
            return "Stack is Empty"
        delete_head = self.head
        self.head = self.head.next
        return delete_head.data

    def peek(self):
        if self.is_empty():
            return "Stack is Empty"
        return self.head.data

    # is_Empty 기능 구현
    def is_empty(self):
        return self.head is None

• 실제 파이썬에서는 list를 이용해서 스택으로 사용

❓

Q. 수평 직선에 탑 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] # 다음과 같이 반환하시면 됩니다!

• 맨 뒤에거가 없어지니까 스택 을 활용했다고 생각하면 된다.

top_heights = [6, 9, 5, 7, 4]


def get_receiver_top_orders(heights):
    answer = [0] * len(heights) # [0, 0, 0, 0, 0]
    while heights: # heights가 빈 상태가 아닐때 까지
        height = heights.pop()
        for idx in range(len(heights) -1, 0, -1):
            if heights[idx] > height:
                answer[len(heights)] = idx + 1
                break
                # 7의 높이를 가진 레이저에 부딪히는 것을 알았기에 해당 7의 인덱스인 4를 answer의 맨 마지막 원소에 넣어야 함.
                # idx + 1은 위치를 알려주길 원했기 때문
                # answer에 넣으려면 하나 뺀것에 대한 것 더하기 1 이므로 인덱스로 해서 현재 나와 있는 스택의 길이로 함.
    return answer


print(get_receiver_top_orders(top_heights))  # [0, 0, 2, 2, 4] 가 반환되어야 한다!

• O(N^2)이 총 시간복잡도