[programmers] 프로그래머스 탑(Python)

(주)그렙

[programmers] 프로그래머스 탑

(Python)

(글쓴날 : 2020.06.11)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 탑

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42588

코딩테스트 연습 - 탑

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

송신 탑에서 왼쪽으로 레이저 신호를 발사하고, 송신 탑보다 높은 수신 탑에서 신호를 받을 때 신호별 수신한 탑의 위치를 구하는 문제입니다.

단, 수신한 탑이 없다면 0으로 표시합니다.

 

저의 경우, 스택을 적용하였고, Python을 사용했습니다.

송신 탑에서 왼쪽으로 레이저 신호를 발사하므로 리스트의 맨 뒤에서부터 탐색을 시작해 만약 신호를 수신하지 못한다면 스택에 저장해놓고 수신 가능한 탑이 발견될 시 꺼내는 식으로 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

def solution(heights):
    answer = [0] * len(heights)
    save  = []
    
    for i in range(len(heights) - 1,-1,-1):
        if not save:
            save.append((heights[i], i))
            continue
        
        while save and save[-1][0] < heights[i]:
            answer[save[-1][1]] = i + 1
            save.pop()
        
        save.append((heights[i], i))
        
    return answer

---