백준 6198번 옥상 정원 꾸미기

지금은 버려진 깃허브 블로그에 작년에 썼던 글을 몇 개 끌어올 예정..
2021년 05월 01일에 썼던 글

---

나의 첫 글은 어떤 것을 써야할까 고민하던 중

일을 하면서 코딩테스트 수준의 문제를 무난하게 풀겠다는 목표로 공부를 하고 있는데

목표를 이루려면 골드문제 정도는 풀면서 연습해야하지 않겠는가

생각하며 야심차게 고른 문제

하지만 골드5 문제도 아직 나에게 힘들었다

골드1 문제도 뚝딱뚝딱 푸는 날이 오기를...

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

요약하면

1. 건물은 일렬로 서 있고 자신의 오른쪽 건물만 볼 수 있다
2. 높이가 같거나 높은 빌딩이 있으면 너머를 볼 수 없다
3. 각 건물에서 관찰할 수 있는 건물의 수를 모두 합하면?

문제에서는 각 건물에서 몇 개의 건물을 관찰할 수 있는지 물어보고 있지만

사실 문제를 해결하기 위해서는 각 건물을 몇 개의 건물에서 볼 수 있는가로 접근해야 했다

간단하게 적었지만 이 결론을 얻기 위해 거친 수 많은 시행착오..

는 생략 (창피)

내가 낸 해결책

일단 스택을 사용해야하는 문제

이유 : 내가 스택을 공부하고 있었고 관련 문제를 검색했기 때문

1. 스택의 top이 자신보다 높은 경우
   • 스택에 들어있는 건물은 다 자신보다 높다 → 스택에 push
2. 자신보다 스택의 top이 낮은 경우
   • pop 한 뒤 스택의 크기만큼 + → 자신보다 더 높은 건물을 만날 때 까지 반복
   • 더 높은 건물을 만나면 push
   • pop하고 난 뒤 스택의 크기만큼 + 하는 이유 → 스택의 top에 있는 건물은 스택에 들어있는 건물 중 top을 제외한 나머지 건물에서 모두 관찰이 가능하다
3. 건물 끝까지 다 처리했는데 스택에 건물이 남아있는 경우
   • 최대 높이보다 더 높은 1000000001층짜리 건물을 마지막에 추가해 2번으로 처리

코드화 하면!

from sys import stdin
from collections import deque

n = int(stdin.readline())

b = [int(stdin.readline()) for i in range(n)]
b.append(1000000001)
s = deque()
cnt = 0

for i in range(n+1):
  if len(s)==0:
    s.append(b[i])
  else:
    if i==n or s[-1]<=b[i]:
      while s[-1]<=b[i]:
        s.pop()
        cnt+=len(s)
        if len(s)==0:
          break 
      s.append(b[i])
    elif s[-1]>b[i]:
      s.append(b[i])
    
    
print(cnt)

사실 글로 정리해보며 적다보니 코드에서 쓸모 없는 부분이 발견되었다

그래서 다시 수정해서 제출해보니 정답이었다

잔디를 심기위한 포스팅이었지만 푼 문제를 한번 더 정리해보는 것이 공부가 되는 것 같다

더 좋은 방법이 있을지는 고민하지 않기로 했다