[백준 22866 🥇] 탑 보기

https://www.acmicpc.net/problem/22866

22866번: 탑 보기

문제풀이

import sys

n=int(sys.stdin.readline())
building=list(map(int, sys.stdin.readline().strip().split(' ')))
building.insert(0,0)

# 스택을 이용해서 좌측으로 볼 수 있는 건물들, 우측으로 볼 수 있는 건물들 확인

count=[0]*(n+1)
# 좌측으로 볼 수 있는 건물 확인
stackL=[]
ansL=[0]*(n+1)
for i in range(1,n+1):
    while stackL and stackL[-1][0]<=building[i]:
        stackL.pop()
    if stackL:
        ansL[i]=stackL[-1][1]
        count[i]+=len(stackL)
    stackL.append((building[i], i))

# 우측으로 볼 수 있는 건물 확인
stackR=[]
ansR=[0]*(n+1)
for i in range(n,0,-1):
    while stackR and stackR[-1][0]<=building[i]:
        stackR.pop()
    if stackR:
        ansR[i]=stackR[-1][1]
        count[i]+=len(stackR)
    stackR.append((building[i], i))

ans=[0]*(n+1)
for i in range(1, n+1):
    if count[i]==0:
        continue
    if ansR[i]!=0 and ansL[i]!=0:
        if (ansR[i] - i) == (i - ansL[i]):
            ans[i] = ansL[i]
        elif (ansR[i] - i) > (i - ansL[i]):
            ans[i] = ansL[i]
        elif (ansR[i] - i) < (i - ansL[i]):
            ans[i] = ansR[i]
    elif ansR[i]==0 and ansL[i]!=0:
        ans[i]=ansL[i]
    elif ansR[i]!=0 and ansL[i]==0:
        ans[i]=ansR[i]


for i in range(1, n+1):
    if count[i]==0:
        print(0)
    else:
        print(count[i], ans[i])

• 어떤 건물을 기준으로 좌측에서 볼 수 있는 건물과, 우측에서 볼 수 있는 건물을 각각 계산해주면 된다.
• https://1eehyunji.tistory.com/entry/%EB%B0%B1%EC%A4%80-2493-%F0%9F%A5%87-%ED%83%91

[백준 2493 🥇] 탑

얼마전에 풀었던 2493번 탑 문제를 응용한 버전같다!

2493의 경우, 한 탑에서 좌측으로 레이저를 쏠 수 있는 건물을 구하기 위해 스택을 사용했다. 

 

이 문제도 동일하게 맨 왼쪽 건물부터 스택에 넣어주며 스택의 top보다 새로 스택에 들어온 건물의 높이가 작을 때까지 스택의 pop을 반복해주고, 반복이 끝났을 때 스택에 건물이 남아있다면 스택의 top이 현재 건물에서 볼 수 있는 가장 가까운 건물이라는 뜻이 된다. 

이러한 이유는 위에 링크를 걸어둔 탑 풀이 게시글에서 확인할 수 있다. 

 

또, 볼 수 있는 건물의 개수를 구해야 하는데, 이때도 반복이 모두 끝나고 stack에 남아있는 건물의 수가 바로 볼 수 있는 건물의 개수를 의미한다. 

이러한 과정을 통해 좌측에서 볼 수 있는 건물의 번호를 저장하고, 좌측에서 볼 수 있는 건물의 개수를 저장한다.

 

그리고 우측에서 볼 수 있는 건물을 보려면 맨 오른쪽 건물부터 스택에 넣어주면서 위와 같은 과정을 한 번 더 반복해주면 된다.

 

그리고 좌측 기준으로 볼 수 있는 가장 가까운 건물의 번호가 저장된 ansL 배열과 우측 기준으로 볼 수 있는 가장 가까운 건물의 번호가 저장된 ansR 배열을 비교해서 최종적으로 가장 가까운 건물의 번호 중에서 가장 작은 번호를 가지는 값을 건물별로 계산해서 ans 배열에 저장해주고, 볼 수 있는 건물의 개수가 저장된 count 배열의 값과 함께 출력해주면 된다.