[Algorithm🧬] 정올 1328 : 빌딩

문제

처음에 생각한 것.. 그냥 전체 비교..

n = int(input())
buildings = [int(input()) for _ in range(n)]
near_buildings = [0] * n

for i, b in enumerate(buildings):
    for next in range(i + 1, n):
        if buildings[next] > b:
            near_buildings[i] = next + 1
            break

for i in range(n):
    print(near_buildings[i])

시간 초과..

n = int(input())
buildings = [int(input()) for _ in range(n)]
near_buildings = [0] * n

stack = []

# 처음꺼 넣고


for i, height in enumerate(buildings):
    if not stack:
        stack.append((i, height))

    # 옆 건물이 stack 의 맨 위보다 작거나 같으면 스택에 계속 넣음 (안보이니까)
    elif stack[-1][1] >= height:
        stack.append((i, height))

    # stack 의 맨 위보다 큰 건물이 나타나면
    else:
        # 스택에 들어있는 큰 건물보다 작은 건물을 모두 빼고 해당 건물을 넣는다. (해당 건물과 크거나 같은 건물이 나타날 때까지)
        while stack and stack[-1][1] < height:
            t = stack.pop()
            near_buildings[t[0]] = i + 1
        stack.append((i, height))

for i in range(n):
    print(near_buildings[i])

진심으로 스택을 여기서 어떻게 쓰지 싶어서 인터넷 찾아서 참고했다... 보고 보니까 옛날에 푼 문제 중에 비슷한 유형 있는데... 조금만 쉬어도 이렇게 기억이 안날수가...🫠🫠🫠

앞에서부터 하나씩 가면서 그 빌딩이 보는걸 기준으로.. 그러면

3
3 2 (2는 작거나 같아서 3에게 안보임)
3 (6은 커서 2에게 보임)
(6은 커서 3에게 보임)
6
6 1 (1은 작아서 6에게 안보임)
6 1 1 (1은 작거나 같아서 1에게 안보임)
6 1 (2 는 커서 1에게 보임)
6 (2는 커서 1에게 보임)
6 2 (2는 작아서 6에게 안보임)

나머지 2개는 볼 수 있는 건물이 없고
3 2 는 3번건물 6을 4 5 는 6번건물 2를 볼 수 있음.
이걸 중간에 배열에 기록해두면 답.

아래는 생각해보니까 stack.append((i, height)) 가 겹쳐서 if stack[-1][1] > height 대신 while 문으로 그냥 처음부터 걸러버릴 수 있어서 아래처럼 짰다.

import sys
readl = sys.stdin.readline

n = int(readl())
buildings = [int(readl()) for _ in range(n)]

stack = []
show = [0] * n

for idx, b in enumerate(buildings):
    if len(stack) == 0:
        stack.append((idx, b))

    while stack and stack[-1][1] < b:
        i, _ = stack.pop()
        show[i] = idx + 1
    stack.append((idx, b))

print(*show, sep='\n')