[백준] 6198번 - 옥상 정원 꾸미기

1. 문제 한 줄 요약

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

 

각 빌딩에서 오른쪽을 보면서 자신보다 높거나 같은 빌딩이 나오기 전까지 볼 수 있는 빌딩 수의 총합을 구하는 문제.

---

2. 처음 접근 (실패한 방법)

처음에는 이렇게 생각했다.

"각 빌딩마다
→ 나보다 큰 빌딩이 처음 나오는 위치를 찾으면
→ 그 전까지 개수를 세면 되지 않을까?"

그래서 다음과 같이 접근했다:

• 오른쪽 빌딩들을 스택으로 관리
• 뒤에서부터 순회하면서
• stack[-1][index] - 현재 index로 개수를 계산

memo[i] = stack[-1][0] - i

---

3. 왜 틀렸는가

이 방식은 겉보기엔 맞아 보이지만 핵심적인 문제가 있다.

 1) “가장 가까운 큰 빌딩 하나”만 보면 안 됨

이 문제는 단순히

“막는 빌딩 위치 하나 찾기”

가 아니라

“막히기 전까지 몇 개를 볼 수 있는지 누적 계산”

이 중요하다.

---

 2) 작은 빌딩들을 버리면 안 됨

초기 코드에서는 이런 로직이 있었다:

 

if stack[-1][1] <= building[i]:
	stack.append(...)

 

이건 사실상
→ 작은 빌딩들을 계속 버리는 구조

하지만 문제에서는:

→ 작은 빌딩도 "볼 수 있는 대상"이기 때문에
→ 절대 버리면 안 된다

---

 3) 인덱스 차이 = 개수 X

 

stack[-1][0] - i

 

이건 단순 거리일 뿐이지

→ 중간에 막히는 빌딩이 있는지 고려하지 못함

---

4. 핵심 깨달음

이 문제의 본질은 이거였다:

 "각 빌딩이 보는 개수"를 직접 구하려 하지 말고
 "현재 빌딩을 볼 수 있는 이전 빌딩 수"로 바꿔서 생각하자

---

5. 발상의 전환

문제:

• i번 빌딩이 오른쪽을 본다

→ 반대로 생각하면:

현재 빌딩을
→ 왼쪽에 있는 어떤 빌딩들이 볼 수 있는가?

이걸 누적하면 같은 결과가 나온다.

---

6. 해결 아이디어 (단조 스택)

핵심 전략:

1. 왼쪽 → 오른쪽으로 순회
2. 스택에는 내림차순(큰 → 작은) 유지
3. 현재 빌딩보다 작거나 같은 값은 pop
4. 남아 있는 스택의 크기 = 현재 빌딩을 볼 수 있는 빌딩 수

---

스택에 남아 있는 빌딩들은:

• 현재 빌딩보다 모두 높다
• 중간에 가려지지 않는다

→ 즉, 현재 빌딩을 "볼 수 있는" 빌딩들이다

---

7. 최종 코드

import sys
input = sys.stdin.readline

n = int(input())
building = [int(input()) for _ in range(n)]

stack = []
answer = 0

for h in building:
    while stack and stack[-1] <= h:
        stack.pop()
    answer += len(stack)
    stack.append(h)

print(answer)

---

8. 시간복잡도

• 각 원소는 스택에 한 번 push, 한 번 pop
• 총 O(N)

→ N ≤ 80,000 충분히 통과