[백준 알고리즘] 6198번 옥상 정원 꾸미기, 파이썬(python)

6198, 옥상 정원 꾸미기

📁 문제 출처

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

 

💡 생각

• 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그다음에 있는 모든 빌딩의 옥상은 보지 못한다.
• 자신의 오른쪽 빌딩만 볼 수 있다.
• 2493과 비슷한 문제이다. 스택을 이용하지 않으면 시간 초과가 발생할 것을 알면서도 2중 for문으로 일단 풀어보았다.

 

시간 초과

n = int(input())

ans = 0
arr = []

for i in range(n):
    arr.append([i, int(input())])

for i in range(n-1):
    for j in range(i+1, n):
        if arr[i][1] > arr[j][1]:
            ans += 1
        elif arr[i][0] < arr[j][1]:
            break

print(ans)

• 시간 초과 코드에서 스택을 어떻게 사용할까 고민했다. 뭔가가 떠오를 듯 말 듯 하다가 결국엔 다른 사람 풀이를 참고했다. 그리고 여러 풀이를 보고 이해할 수 있었다.

 

🛠 나의 코드

n = int(input())

arr = [int(input()) for i in range(n)]
stk = []
ans = 0

for i in range(n):
    while stk and stk[-1] <= arr[i]:
        stk.pop()

    stk.append(arr[i])
    ans += len(stk) -1

print(ans)

• stk에 값이 있고 stk[-1]가 arr[i]보다 작으면 pop
  • arr[i]건물 옥상을 볼 수 없으니까
• 쉽게 생각하면 ans에 더해주는 값은 arr[i]번째 건물을 볼 수 있는 다른 건물의 수를 더해주는 거다.
  • 0 1 1 2 0 1 이런 식으로 더해준다.
  • len(stk) -1해주는 이유는 자기 자신 빼기

 

✔️ 배운 점 및 주의할 점

• 내가 너무 복잡하게 생각했나? 다른 코드를 봤는데 너무 간단해서 허탈했다.
• 하지만 저런 간단한 코드를 생각하기까지가 어렵고 복잡하다.. ㅎㅎ

 

📌 참고한 코드

• https://bunnnybin.tistory.com/entry/%EB%B0%B1%EC%A4%80-6198-%EC%98%A5%EC%83%81-%EC%A0%95%EC%9B%90-%EA%BE%B8%EB%AF%B8%EA%B8%B0-C-with-monotone-stack
• https://b-programmer.tistory.com/171
• https://jinho-study.tistory.com/801