[백준] 22866번 파이썬

문제링크 : https://www.acmicpc.net/problem/22866

난이도: GOLD III

문제해결 아이디어

• n^2은 시간 초과
• 자신보다 큰 건물만 볼 수 있다.
• 오른쪽이랑 왼쪽을 따로 계산
• 이미 순회한 건물들은 stack 보관, stack에서 자신 보다 작은 건물들은 pop 하면서 내림차순을 만든다
• 이때 stack에는 idx를 보관하여 근접인덱스를 수월하게 구하게 한다.

소스코드

import sys
input = sys.stdin.readline

# n^2은 시간 초과
# 자신보다 큰 건물만 볼 수 있다.
# 오른쪽이랑 왼쪽을 따로 계산
# 이미 순회한 건물들은 stack 보관, stack에서 자신 보다 작은 건물들은 pop 하면서 내림차순을 만든ㄷ
# 이때 stack에는 idx를 보관하여 근접인덱스를 수월하게 구하게 한다.


n = int(input())
height = list(map(int, input().split()))
cnt = [0]*n
near = [int(1e9)]*n

# 왼쪽 계산
stack = []
for idx, j in enumerate(height):
    while stack:
        if height[stack[-1]] <= j: # 자신보다 작은 건물들은 stack에서 제거
            stack.pop()
        else:
            if abs(idx-near[idx]) > abs(idx-stack[-1]):
                near[idx] = stack[-1]
            
            break
    cnt[idx] += len(stack)
    stack.append(idx)

# 오른쪽 계산
stack = []
for idx, j in enumerate(reversed(height)):
    idx = n-1-idx
    while stack:
        if height[stack[-1]] <= j:
            stack.pop()
        else:
            if abs(idx-near[idx]) > abs(idx-stack[-1]):
                near[idx] = stack[-1]

            break
    cnt[idx] += len(stack)
    stack.append(idx)

for i in range(n):
    print(cnt[i], near[i]+1) if cnt[i] != 0 else print(cnt[i])