[백준/Python] 옥상 정원 꾸미기

📄 문제

백준
난이도 : Gold 5
문제 제목 : 옥상 정원 꾸미기

✏️ 풀이 1

import sys

n = int(sys.stdin.readline())
heights = [int(sys.stdin.readline()) for _ in range(n)]
answer = 0
# 시야를 막을 후보군들 (idx, height, can_see)
stack = []

for i in range(n - 1, -1, -1):
    current_can_see = 0
    while stack:
        if stack[-1][1] < heights[i]:
            tmp = stack.pop()
            current_can_see += tmp[2] + 1
        else:
            break
    stack.append((i, heights[i], current_can_see))
    answer += current_can_see
print(answer)

'관리인이 보는 방향'의 끝인, 가장 오른쪽 옥상부터 for문을 돌면서 볼 수 있는 옥상 수를 찾는 풀이이다.
➕ '오른쪽으로만 볼 수 있다'는 점에서 스택을 사용해야 한다는 힌트를 얻었다.

✅ 풀이 한 줄 설명:
우선 stack이라는 빈 스택을 선언한 뒤, 오른쪽 빌딩부터 ({index}, {building_height}, {can_see_num}))을 삽입하면서 시야를 막지 않는 작은 빌딩들을 제거해 나가는 방법으로 풀었다.

✅ stack = [] : 가장 오른쪽 빌딩부터 ('인덱스', '높이', '해당 빌딩에서 볼 수 있는 빌딩 수')를 저장하되,
앞으로 나올 빌딩들에 대해 시야를 막을 직접적인 후보군이 되지 못 한다는 것(왼쪽 빌딩에 비해 키가 작은 빌딩이라는 것)이 확인되면 pop() 해주어 스택에서 제거한다.

✅ 자세한 풀이 설명:

1. for문을 돌며 오른쪽 빌딩부터 해당 빌딩보다 키가 작은(해당 빌딩이 볼 수 있는) 빌딩이 stack에 존재하는지 확인한다.
   • 키가 작은 빌딩을 찾았다면, 찾은 빌딩은 앞으로 현재 빌딩에 가려져서 보이지 않을 것이다. 따라서 tmp = stack.pop()을 한다.
     그리고 현재 빌딩은 찾은 빌딩이 볼 수 있었던 빌딩까지 포함하여 볼 수 있기 때문에, current_can_see += tmp[2] + 1을 해준다.
   • 만약 stack[-1]의 빌딩이 현재 빌딩보다 키가 크거나 같다면, 더 이상 현재 빌딩은 다른 빌딩 옥상을 볼 수 없다. (시야가 막힘) 따라서 while문을 break한다.
2. while문을 벗어나면 시야를 막는 빌딩을 찾았다는 뜻이거나, 혹은 모든 빌딩을 다 볼 수 있었다는 뜻이다. 따라서 이제 현재 빌딩을 stack에 추가하여 다음 loop 빌딩의 시야를 막을 후보군으로 넣어주어야 한다.
   (stack.append((i, heights[i], current_can_see)))
   • 만약 다음 loop 빌딩(i - 1)보다 현재 빌딩(i)이 키가 크다면, 현재 빌딩은 다음 loop에서도 그대로 stack에 있을 것이다.
   • 만약 다음 loop 빌딩(i - 1)보다 현재 빌딩(i)이 키가 작다면, 현재 빌딩은 다음 loop에 진행 시 stack에서 제거될 것이다.
3. 다음 loop로 가기 전에, answer += current_can_see를 해준다.

✏️ 풀이 2

import sys

n = int(sys.stdin.readline())
heights = [int(sys.stdin.readline()) for _ in range(n)]
answer = 0
stack = []

for i in range(n):
    x = heights[i]
    while stack and stack[-1] <= x:
        stack.pop()
    answer += len(stack)
    stack.append(x)
print(answer)

다른 사람의 풀이인데, '✏️ 풀이 1'은 현재 빌딩이 볼 수 있는 빌딩 수를 구한 풀이라면 이 풀이는 현재 빌딩을 볼 수 있는 빌딩 수를 구한 풀이이다.
즉, answer에 더해주는 값은 heights[i] 빌딩을 볼 수 있는 다른 건물의 수이다.
따라서 stack에는 현재 빌딩보다 키가 같거나 작은 빌딩은 제거하여 키가 큰 빌딩만 존재할 것이다. (현재 빌딩(heights[i])보다 키가 크더라도 오른쪽에 본인보다 큰 빌딩이 있으면 현재 빌딩을 못 보기 때문에 이런 빌딩도 stack에서 제거된다.)

📦 GitHub

해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Gold) '6198. 옥상 정원 꾸미기'
GitHub - [5강] 스택/응용문제 '6198. 옥상 정원 꾸미기'

---

처음에는 역시나 가장 흔하고 쉬운 방법인 2중 for문 풀이가 생각났다. 하지만 바로 이전에 '백준 2493. 탑' 문제를 풀어 스택으로 풀어야 시간초과가 안 날 것임을 직감하고 스택 풀이 방법을 생각해냈다.
스택 풀이 방법을 생각해낼때, 처음에는 스택에 빌딩 정보를 ('인덱스', '높이')만 넣는 방향으로 생각했었다. 그러나 그렇게 하면 2중 for문과 같은 시간복잡도가 나올 것이라 판단하였다.
따라서 필요없을 빌딩(시야를 막는 후보군이 될 수 없는 작은 빌딩들)을 스택에서 제거하는 방식으로 구현해야 겠다는 생각이 들었고, 이를 위해 스택에 빌딩 정보를 저장할 때 ('인덱스', '높이', '해당 빌딩에서 볼 수 있는 빌딩 수')로 저장을 해야겠다는 판단을 하였다.

➕ 다른 사람의 풀이를 한 번 찾아보니 보통 '✏️ 풀이 2'처럼 푼 것을 보고 해당 풀이도 추가하였다. 해당 빌딩이 볼 수 있는 빌딩 수를 구하는 방법만 생각했었는데,
해당 빌딩을 볼 수 있는 빌딩 수를 구하는 방법으로도 생각할 수 있다는 것을 깨달았다.
앞으로는 지문에 나온 방법에 갇히지 말고, 다양한 방면으로 문제를 바라봐야겠다.