[자료구조] 스택 문제 (탑) python

문제

Q. 수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한 ,한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4 인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다.
그러면, 탑은 다음과 같이 신호를 주고 받습니다.

높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑에서 수신하고,
높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이,
높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다.

높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는
어떤 탑에서도 수신할 수 없습니다.

이 때, 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 반환하시오.

---

해결

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


def get_receiver_top_orders(heights):
    # 위치 배열 생성
    answer = [0] * len(heights)

    # 역순으로 순회
    while heights:
        height = heights.pop()  # 스택에서 하나 빼기
        for index in range(len(heights)-1, 0, -1):
            if heights[index] > height:
                answer[len(heights)] = index+1
                break
    return answer


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

print("정답 = [0, 0, 2, 2, 4] / 현재 풀이 값 = ",get_receiver_top_orders([6,9,5,7,4]))
print("정답 = [0, 0, 0, 3, 3, 3, 6] / 현재 풀이 값 = ",get_receiver_top_orders([3,9,9,3,5,7,2]))
print("정답 = [0, 0, 2, 0, 0, 5, 6] / 현재 풀이 값 = ",get_receiver_top_orders([1,5,3,6,7,6,5]))

• 스택에 있는 데이터가 전부 pop될 때 까지 반복하고, 하나씩 데이터를 빼온 후, 빼온 데이터와 스택에 남아있는 데이터를 역순으로 순회하며 비교한다.
  • 스택에 있는 데이터가 더 크면 탑 위치 배열에 몇번째 탑인지 번호를 넣는다.

[출력]
정답 = [0, 0, 2, 2, 4] / 현재 풀이 값 =  [0, 0, 2, 2, 4]
정답 = [0, 0, 0, 3, 3, 3, 6] / 현재 풀이 값 =  [0, 0, 0, 3, 3, 3, 6]
정답 = [0, 0, 2, 0, 0, 5, 6] / 현재 풀이 값 =  [0, 0, 2, 0, 0, 5, 6]