알고리즘 풀이: [프로그래머스] 탑

https://programmers.co.kr/learn/courses/30/lessons/42588

코딩테스트 연습 - 탑

 

문제 설명

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

 

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

 

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

 

맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

heights는 길이 2 이상 100 이하인 정수 배열입니다.

 

모든 탑의 높이는 1 이상 100 이하입니다.

 

신호를 수신하는 탑이 없으면 0으로 표시합니다.

 

입출력 예

numbers	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]

 

입출력 예 설명

입출력 예 #1

앞서 설명한 예와 같습니다.

 

입출력 예 #2

[1,2,3] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.

[4,5,6] 번째 탑이 쏜 신호는 3번째 탑이 수신합니다.

[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

 

입출력 예 #3

[1,2,4,5] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다.

[3] 번째 탑이 쏜 신호는 2번째 탑이 수신합니다.

[6] 번째 탑이 쏜 신호는 5번째 탑이 수신합니다.

[7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

---

문제 풀이

입력으로 제공된 heights를 역순으로 순회하면서 탑에 대한 정보(높이, 인덱스)를 추출합니다. 추출된 현재 탑의 높이와 스택에 저장된 이전 탑의 높이를 비교합니다. 높이 비교를 통해 현재 탑이 이전 탑에서 송신한 신호를 수신할 수 있는지 파악합니다. 높이 비교와 함께 스택 연산(push, pop)도 수행합니다.

 

 

그림을 통해 송수신 조건에 따른 스택의 동작 과정을 살펴보아요.

0단계(준비): 스택 및 필요한 자료구조 초기와 및 조건 정의

heights는 입력으로 제공된 탑의 높이로 height[N-1]에 저장된 값은 N번째 탑의 높이입니다. 문제 해결을 위해서 heights를 역순으로 순회합니다. reveiver는 송수신 정보를 관리하는 리스트입니다. receiver[N-1]의 값은 N번째 탑에서 보낸 신호를 수신한 탑의 인덱스입니다.

 

 

여기서 탑의 인덱스에 대해서 확실하게 구분하여 정의할 필요가 있어요.

 

탑의 인덱스는 0부터 증가하는 체계와 1부터 증가하는 체계로 나뉩니다. receiver 리스트나 heights 리스트에서 탑을 가리키는 인덱스는 일반적인 프로그래밍에서의 인덱스처럼 0부터 시작합니다. 이를 0 체계 인덱스라고 부르도록 합니다. 하지만 문제 정의상 탑은 0번째 탑이 아닌 1번째 탑에서부터 시작합니다. 이렇게 탑의 이름과 관련되어서 1부터 시작하는 인덱스를 1 체계 인덱스라고 부르도록 합니다.

 

0 체계 인덱스와 1 체계 인덱스는 모두 탑의 송수신 정보를 관리하는 receiver 리스트에서 사용합니다. 0 체계 인덱스는 receiver 리스트에서 탑을 가리키기 위한 용도로 사용하고, 1 체계 인덱스는 receiver 리스트의 원소 값으로 사용한다. 예를 들어 N번째 탑에서 보낸 신호가 M번째 탑에서 수신된 상황을 가정해봅시다. N 번째 탑의 0 체계 인덱스인 N - 1로 receiver[N-1]에 N번째 탑에 대한 정보를 할당합니다. N번째 탑에서 보낸 신호가 M번째 탑에서 수신되었으므로 receiver[N-1] 원소의 값은 1 체계 인덱스인 M이 됩니다. 

 

 

이전 탑에 대한 정보를 관리하기 위해서 스택(stack)을 사용해요.

 

스택에는 탑의 높이와 0 체계의 인덱스가 높이에 대한 오름차순으로 저장되어있습니다.

 

heights를 역순으로 순회하면서 스택에 저장된 탑에서 보낸 신호 중 현재 탑에 의해서 수신될 수 있는 신호가 있는지 판단합니다.

 

만약 스택 top에 저장된 탑의 높이가 현재 탑의 높이보다 높다는 것은 이전 탑의 높이가 현태 탑의 높이보다 높다는 것을 의미합니다. 따라서 이전 탑에서 보낸 신호는 현재 탑에 의해서 수신되지 않는다. 나아가 스택 top은 높이가 가장 낮은 탑에 대한 정보를 저장하기 때문에 스택의 다른 요소와 현재 탑의 높이를 비교할 필요는 없습니다.

 

반면에 현재 탑의 높이가 스택 top에 저장된 탑의 높이보다 크다면 현재 탑이 이전 탑의 신호를 수신할 수 있습니다. 이러한 경우 스택의 top을 pop 합니다. 그리고 다시 스택 top에서의 높이와 현재 높이를 비교합니다. 이 과정은 스택이 비거나 스택 top에 저장된 탑의 높이가 현재 탑의 높이보다 높을 때까지 반복합니다.

 

heights를 역순으로 반복하는 것의 마무리는 현재 높이와 0 체계 인덱스를 스택에 push 하는 것입니다.

 

 

1단계: 높이가 4인 다섯 번째 탑

1단계: 현재 탑의 높이 4

heights를 역순으로 조회하는 과정에서 첫 번째 반복은 높이가 4인 다섯 번째 탑(0 체계 인덱스로는 인덱스가 4인 탑)입니다. 현재 스택은 비어 있습니다. 신호를 보내고 대기하는 탑이 없으므로 현재 탑에서 신호를 보냅니다(현재 탑의 높이와 0 체계의 인덱스를 스택에 push).

 

 

2단계: 높이가 7인 네 번째 탑

2단계: 현재 탑의 높이 7

두 번째 단계는 높이가 7인 네 번째 탑입니다. 현재 스택 top을 살펴보면 높이가 4인 다섯 번째 탑이 저장되어 있습니다. 네 번째 탑의 높이(7)가 스택에 저장된 다섯 번째 탑의 높이(4)보다 크기 때문에 다섯 번째 탑에서 보낸 신호는 네 번째 탑에 의해서 수신 완료됩니다. 이러한 경우 스택에서 top을 pop 하고 송수신 정보를 관리하는 receiver 리스트를 갱신합니다. 다섯 번째 탑은 0 체계 인덱스가 4이므로 receiver[4]의 값은 현재 탑의 1 체계 인덱스 4가 됩니다.

 

2단계: 현재 탑의 높이 7

스택 top을 pop 했기 때문에 현재 스택은 비어있고 따라서 현재 탑에 대한 정보를 스택에 push 합니다.

 

 

3단계: 높이가 5인 세 번째 탑

3단계: 현재 탑의 높이 5

세 번째 탑의 높이는 5로 스택 top에서 관리하는 높이 7보다 작습니다. 이전 탑의 높이가 현재 탑의 높이보다 높은 경우로 이전 탑의 신호는 현재 탑에 의해서 수신되지 않습니다. 현재 탑에 대한 높이와 인덱스가 스택에 push 되고 반복을 종료합니다.

 

 

4단계: 높이가 9인 두 번째 탑

 

4단계: 현재 탑의 높이 9

4단계: 현재 탑의 높이 9

현재 탑의 높이가 9이고 스택의 top의 높이는 5와 7입니다. 이는 모두 현재 탑의 높이보다 작으로 수신 대기 중이었던 모든 탑의 신호들은 현재 탑에 의해서 수신됩니다. 이를 receiver 리스트에 반영합니다.

 

4단계: 현재 탑의 높이 9

 

스택에서 수신 대기 중인 모든 탑에 대한 정보가 pop 되었으므로 스택은 빈 상태가 되고, 현재 탑에 대한 정보를 스택에 push 합니다.

 

 

5단계: 높이가 6인 첫 번째 탑

5단계: 현재 탑의 높이 6

현재 탑의 높이 6이 스택 top의 높이 9보다 작으므로 현대 탑에 의해서 수신될 수 있는 신호를 보낸 탑이 없습니다. 따라서 현재 탑에 대한 정보를 스택에 push 하고 반복을 종료합니다.

 

최종적으로 송수신 정보를 가지고 있는 receiver리스트를 반환하면 문제를 해결합니다.

최종단계

 

소스 코드

메인 솔루션 함수

def solution(heights):
    receiver = [0] * len(heights)
    stack = list()
    for idx in range(len(heights) - 1, -1, -1):
        idx_one = idx + 1
        height = heights[idx]
        while stack and height > stack[-1][0]:
            top_height, top_idx = stack.pop(-1)
            receiver[top_idx] = idx_one
        
        stack.append((height, idx))
    
    return receiver

 

문제 해결 화면

 

github 주소: github.com/dhsong95/-PRACTICE-Programmers-Algorithm/blob/master/level%202/탑.py

dhsong95/-PRACTICE-Programmers-Algorithm