파이썬 알고리즘 290번 | [백준 6198번] 옥상정원 - 스택

290. 옥상정원

1) 어떤 전략(알고리즘)으로 해결?

스택
그리디

2) 코딩 설명

<내 풀이>

• 2023 0106 풀이 - 이번엔 해설 안보고 풀었다 ㅎㅎ

관점 : 나(i번째 빌딩)를 볼 수 있는 빌딩의 수를 누적해서 더하기

• stk 에 맨 앞 빌딩부터 담아준다.
• i번째 빌딩차례 때 stk(내 앞에 있는 빌딩들) 중 나를 지켜볼 수 있는 (나보다 큰 애들) 건물만 stk에 남겨두고 pop (pop 대상은 나보다 작거나 같은 애들 == 내가 더 크거나 같은 애들) 해버린다.
• 그럼 i번째 stk에는 나를 지켜볼 수 있는 건물수만 남으므로 이를 answer에 누적해서 더해준다.

import sys

n = int(sys.stdin.readline().rstrip())
building = []
answer = 0
stk = []

for i in range(n) :
    height = int(sys.stdin.readline().rstrip())
    building.append((i,height))

for i in range(n) : 
    
    now_number , now_height = building[i]
    
# i번째 빌딩차례 때 stk(내 앞에 있는 빌딩들) 중 
# 나를 지켜볼 수 있는 (나보다 큰 애들) 건물만 
# stk에 남겨두고 , 아니라면 pop 
# (pop 대상은 나보다 작거나 같은 애들 == 내가 더 크거나 같은 애들)

    while stk and stk[-1][1] <= now_height :
        stk.pop()
    answer+=len(stk)
    stk.append((now_number, now_height))

print(answer)

---

6198 - (2022 0503 풀이
출처 : https://lakelouise.tistory.com/62?category=1006962

• 관점을 어떻게 설정했어야 했니?
  => 빌딩 기준으로, 나보다 이전 빌딩 중에서 날 볼 수 있는 애들을 collect 시켜주고, 이를 벗어나는 기준인 나보다 크거나 같은 애 만나면 더 이상 그 건물의 더 예전 건물은 나를 보지 못함

n = int(input())
 
arr = [int(input()) for i in range(n)]
stk = []
ans = 0
#stack에 담기게 되는 것 : 
# 1) 나보다 이전 건물
# 2) 나보다 작은 건물 (내가 더 크거나 같음)

for i in range(n):
    while stk and stk[-1] <= arr[i]:
        # 내 이전 건물 중에서
        # 나보다 큰 건물 만나면 stop
        
        stk.pop()
 
    stk.append(arr[i])
    ans += len(stk) -1
    # 나를 이전 건물로 윗 줄에서 등록해주니깐 
    # 나 자신은 빼줘야지 -1
 
print(ans)

<반성 점>

---

옛날에 느낀 반성점 (2022 0503)

• 6198 경우는, 이중 for 안쓰고도 가능할 거라고 생각하긴 했는데 , 아이디어를 생각해내지 못한 게 아쉽다.
• 경비원의 eye 관점이 아닌, 건물의 관점에서 나를 바라보는 경비원을 고려한 것이 너무 감명깊은 아이디어다. 계속해서 머리 아프게 나도 아이디어를 배우고 흡수해나가고 싶다.

---