백준 6198 | 옥상 정원 꾸미기 | python 풀이

문제

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

6198번: 옥상 정원 꾸미기

도시에는 N개의 빌딩이 있다.

빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다.

i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으로만 볼 수 있다.

i번째 빌딩 관리인이 볼 수 있는 다른 빌딩의 옥상 정원은 i+1, i+2, .... , N이다.

그런데 자신이 위치한 빌딩보다 높거나 같은 빌딩이 있으면 그 다음에 있는 모든 빌딩의 옥상은 보지 못한다.

 

예) N=6, H = {10, 3, 7, 4, 12, 2}인 경우

• 1번 관리인은 2, 3, 4번 빌딩의 옥상을 확인할 수 있다.
• 2번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 3번 관리인은 4번 빌딩의 옥상을 확인할 수 있다.
• 4번 관리인은 다른 빌딩의 옥상을 확인할 수 없다.
• 5번 관리인은 6번 빌딩의 옥상을 확인할 수 있다.
• 6번 관리인은 마지막이므로 다른 빌딩의 옥상을 확인할 수 없다.

따라서, 관리인들이 옥상정원을 확인할 수 있는 총 수는 3 + 0 + 1 + 0 + 1 + 0 = 5이다.

내 답안

import sys as s
n = int(s.stdin.readline().strip())
height = [int(s.stdin.readline().strip()) for _ in range(n)]

stack = []
cnt = 0

for cur in height:
  while stack and stack[-1] <= cur:
    stack.pop()  # 옥상을 볼 수 없는 관리인은 전부 제거

  cnt += len(stack) # 옥상을 볼 수 있는 관리인 수
  stack.append(cur)  # 현 빌딩을 스택에 추가

print(cnt)

해설

스택 문젠데 생각보다 어려웠다!

처음엔 완전탐색으로 풀어서 답은 나왔지만 당연히 시간초과가 났었고 스택을 활용할 수 있는 방법은 도저히 떠오르지 않았다. 결국 1시간 정도 고민하다가 다른 사람의 풀이를 참고했다.

 

풀이의 핵심은 stack의 길이 즉, stack 안의 원소 개수를 활용하는 것이다.

그리고 주어진 빌딩 리스트의 원소를 순회하면서 본인이 볼 수 있는 옥상의 수가 아니라, 본인을 볼 수 있는 관리인의 수를 구해야 한다.

 

문제 풀이에 활용할 stack을 준비하고 height = [10, 3, 7, 4, 12, 2] 라고 하자.

10부터 시작해서, stack 안에 들어간 빌딩 중 자신을 볼 수 있는 빌딩 관리인의 수를 찾는다.

 

이 과정을 height의 원소마다 수행해주면 된다.

 

cur	stack	cur을 볼 수 있는 빌딩 관리인의 수
10	10	0
3	10, 3	1
7	10, 7	1
4	10, 7, 4	2
12	12	0
2	12, 2	1

 

원소별로 구한 관리인의 수를 공용 변수 cnt에 더해줌으로써 최종 출력값을 계산한다.

 

 

피드백

• 스택을 활용한 다양한 문제를 접해보면서 스스로 풀이법을 찾는 연습이 필요한 것 같다.