[백준/Python] 2493번 - 탑

import sys
input = sys.stdin.readline

n = int(input())
b = list(map(int, input().split()))

## 틀린 풀이
# 수신한 탑들의 번호 출력
result = [0]
h = 0 # 가장 높은 빌딩의 index
for i in range(1,n):
  if b[h] > b[i]:
    result.append(h+1)
  else:
    result.append(0)

  # 뒤 차례 기준, 가장 가깝고 + 높은 빌딩
  if i != n -1 and b[i] > b[i + 1]:
    h = i

print(*result)

처음에 했던 틀린 풀이...

틀렸습니다가 떴다. 당연했던게 바로 왼쪽 빌딩 1개만 보고, 현재 빌딩보다 높지않으면 0을 넣어준다.

왼쪽에 있는 다른 빌딩 중에 현재 빌딩보다 높은 빌딩이 있을 수도 있기 때문에 바로 0을 넣어주면 안된다!!

 

 

결국 알고리즘 분류보고 스택 문제라는 힌트를 가지고 풀었다.

import sys
input = sys.stdin.readline

n = int(input())
b = list(map(int, input().split()))

result = [0]
stack = [0] # index를 stack으로 쌓기
for i in range(1, n):
  while stack and b[stack[-1]] <= b[i]:
    stack.pop()
  
  if not stack:
    result.append(0)
  else:
    result.append(stack[-1]+1)
  
  stack.append(i)

print(*result)

풀이 과정

1. 먼저 index를 결과로 쌓아야 하기 때문에 stack도 index로 쌓았다.
2. 스택의 맨 위(가장 가까운 왼쪽 빌딩)의 높이가 현재 빌딩 높이보다 낮으면 스택에서 제외하면서, 왼쪽에서 나보다 높은 빌딩을 찾는다.
3. 높은 빌딩을 찾지 못하면 stack은 결국 empty가 될 것이고, 그럴 경우 수신을 할 빌딩이 없는 것이므로 결과에 0 을 추가한다.
   높은 빌딩을 찾았다면 stack에 남아있는 index가 있을 것이고, 해당 빌딩이 신호를 수신할 빌딩이 되므로 결과에 햔제 index+1을 추가한다(빌딩 index는 1부터 시작이라서 +1)
4. 그리고 현재 빌딩 index를 추가한다.