[프로그래머스] 스택/큐 - 탑 (파이썬)

지난 포스팅에서 프로그래머스 해시문제 4개를 모두 마치고 오늘은 스택/큐 문제를 시작하도록 하겠다.

 

 

프로그래머스 스택/큐 - 탑, 문제 확인

문제 설명은 아래와 같다.

 

---

수평 직선에 탑 N대를 세움

모든 탑의 꼭대기에 신호를 송수신하는 장치를 설치

신호는 신호를 보낸 탑보다 높은 탑에서만 수신 가능

한번 수신된 신호는 다른 탑으로 송신되지 않음

탑의 높이를 담은 배열 heights 주어질 때 각 탑이 쏜 신호를 어떤 탑에서 받았는지 기록한 배열을 리턴

신호를 수신하는 탑이 없으면 0으로 표기

 

 

예를 들어, 아래와 같이 높이가 6,9,5,7,4인 다섯개의 탑이 있을 때 왼쪽으로 동시에 레이저 신호를 발사하면 다음과 같이 신호를 주고받게 된다. 즉, 높이가 5(4)가 보낸 신호는 4(7)이 받고, 4(7)이 보낸 신호는 2(9)가 받고, 3(5)가 보낸 신호는 2(9)가 받고 2(9)와 1(6)이 보낸 신호는 어떤 탑에서도 수신할 수 없다.

 

송신탑(높이)	수신 탑(높이)
5(4)	4(7)
4(7)	2(9)
3(5)	2(9)
2(9)	-
1(6)	-

 

 

처음엔 2(9)는 9보다 높은 탑이 없으니 끝나는게 맞는데 1(6)은 쭉 돌아서 2(9)가 받는게 아닌가 헷갈렸는데 그냥 못받는다고 하는 것을 보니 한번만 왼쪽으로 쭉 돌고 끝나는 건가보다. 

 

참고로, 입출력 예를 보면 heights[0] 탑의 경우 받아줄 곳이 없기 때문에 무조건 0이 된다. 그리고 위에서도 보고 잘못 생각할 뻔 했는데 높이 5인 탑의 리턴은 1이 아니라 2이다. (인덱스 1부터 시작)

 

heights	return
[6,9,5,7,4]	[0,0,2,2,4]
[3,9,9,3,5,7,2]	[0,0,0,3,3,3,6]
[1,5,3,6,7,6,5]	[0,0,2,0,0,5,6]

 

 

프로그래머스 스택/큐 - 탑, 문제 풀이 (파이썬)

문제 풀면서 어떻게 해야되지 하다가 range가 역순으로도 돌 수 있다는 것을 처음 알았다. i는 정방향으로 돌고 j는 역순으로 돌면서 (예를들어 i가 3이면, j는 2,1,0) j 탑이 i 탑보다 높이가 높은지 확인한 후 높다면 수신탑(j+1)을 answer에 추가해준다. 그리고 index 변수를 하나 사용해서 더 높은 탑이 없이 끝났는지에 대한 여부를 확인할 수 있게 했다.

 

def solution(heights):
    answer = []
    answer.append(0) 
    for i in range(len(heights)):
        index = 0 #수신여부 체크 변수
        if i == 0: continue #i는 1부터 시작되게 하기
        for j in range(i-1,-1,-1): #i가 3이라면 2,1,0 역순으로 반복문 돌기
            if heights[j] > heights[i]: #더 높은게 있는지 확인
                answer.append(j+1) #수신탑 추가
                index = 1 #수신여부 체크
                break #더 높은게 있다면 이미 수신된거기 때문에 반복문 끝내기
        if index == 0: answer.append(0)  #수신여부가 체크되어 있지 않다면 0을 추가

    return answer

 

 

위 코드로 아래와 같이 채점을 통과할 수 있었다.