[백준] 2439 - 탑 문제 풀이(파이썬,Python)

문제

2493번: 탑

들어가며

이 문제는 스택으로 풀 수 있다.

 

처음 접근은 이전에 풀었던 히스토그램처럼 접근했더니

가볍게 출력초과(시간초과)가 반겨주었다.

 

코드

import sys

input = sys.stdin.readline

n = int(input().strip())
towers = list(map(int, input().strip().split()))

stack = []
result = [0] * n  # 결과를 저장할 리스트 초기화

for i in range(n):
    # 현재 탑보다 낮은 탑은 스택에서 제거
    while stack and towers[stack[-1]] < towers[i]:
        stack.pop()

    # 스택이 비어 있지 않다면, 가장 가까운 왼쪽의 높은 탑의 인덱스를 결과에 저장
    if stack:
        result[i] = stack[-1] + 1  # 0-based index를 1-based로 변환

    # 현재 탑의 인덱스를 스택에 추가
    stack.append(i)

# 결과 출력
print(" ".join(map(str, result)))

풀이

스택에는 현재까지 처리된 탑들의 인덱스를 저장한다.

현재 탑의 높이가 스택에 저장된 마지막 탑의 높이보다 크면, 해당 탑은 신호를 받을 수 없으므로 스택에서 제거한다.

 

다음과 같은 과정을 거치게 된다.

 

입력

5
6 9 5 7 4

 

탑 1 (높이: 6)

1. 현재 탑의 인덱스 : i = 0, 높이 : towers = 6

2. 스택이 비어 있으므로, 이 탑은 신호를 받을 수 있는 왼쪽 탑은 없다.

3. 결과 리스트에서 해당 위치를 바꾸지 않고 0으로 유지한다.

4. 현재 탑의 인덱스를 스택에 추가한다.

 

탑 2 (높이: 9)

1. 현재 탑의 인덱스: i = 1, 높이 : towers = 9

2. 스택에 값이 있고, 현재 탑보다 높이가 낮으므로 pop을 한다.

3. 스택이 비어있기 때문에, 이 탑과 신호를 받을 수 있는 왼쪽 탑은 없다.

4. 결과를 리스트에서 해당 위치를 바꾸지 않고 0으로 유지한다.

5. 현재 탑의 인덱스를 스택에 추가한다.

 

탑 3 (높이: 5)

1. 현재 탑의 인덱스 i = 2, 높이 : towers = 5

2. 스택에 값이 있지만, peek에 있는 값이 현재 탑보다 높으므로 pop을 하지 않는다.

3. 스택이 비어있지 않기 때문에, 이 탑과 신호를 받을 수 있는 왼쪽 탑은 존재한다.

4. peek의 인덱스를 저장한다.

5. 현재 탑의 인덱스를 스택에 추가한다.

 

탑 4 (높이: 7)

1. 현재 탑의 인덱스 i = 3,  높이 : 7

2. 스택에 값이 있고, peek에 있는 값이 현재 탑보다 작으므로 pop을 한다. -> 5가 사라진다.

3. 스택이 비어있지 않기 때문에, 이 탑과 신호를 받을 수 있는 왼쪽 탑은 존재한다. 그게 바로 높이 9인 index 1이다.

4. peek의 인덱스를 저장한다.

5. 현재 탑의 인덱스를 스택에 추가한다.

 

탑 5 (높이:4)

1. 현재 탑의 인덱스 i = 4, 높이 : 4

2. 스택에 값이 있고, peek에 있는 값이 현재 탑 높이보다 크므로 넘어간다.

3. 스택이 비어있지 않기 때문에, 이 탑과 신호를 받을 수 있는 왼쪽 탑은 존재하고, 바로 옆에 있는 peek 탑이다.

4. peek의 인덱스를 저장한다.

5. 현재 탑의 인덱스를 스택에 추가하지만, 모든 탑을 돌았으니 반복문은 종료된다.

 

이때, result에 들어가는 값은 0부터 시작하므로, 실제 결과에 탑의 인덱스를 넣을 땐, +1을 해준다.