[BOJ#6198] 옥상 정원 꾸미기

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

6198번: 옥상 정원 꾸미기

1 초

128 MB

18648

6909

5247

35.248%

문제

 

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

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

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

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

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

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

             = 
 =           = 
 =     -     = 
 =     =     =        -> 관리인이 보는 방향
 =  -  =  =  =   
 =  =  =  =  =  = 
10  3  7  4  12 2     -> 빌딩의 높이
[1][2][3][4][5][6]    -> 빌딩의 번호

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

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

입력

• 첫 번째 줄에 빌딩의 개수 N이 입력된다.(1 ≤ N ≤ 80,000)
• 두 번째 줄 부터 N+1번째 줄까지 각 빌딩의 높이가 hi 입력된다. (1 ≤ hi ≤ 1,000,000,000)

출력

• 각 관리인들이 벤치마킹이 가능한 빌딩의 수의 합을 출력한다.

---

제출 코드

import sys
N = int(input())
bd = []
for _ in range(N):
    bd.append(int(sys.stdin.readline()))
bd.reverse()
stack = []
stack.append(bd.pop())

sumone = 0
while bd:
    if not stack:
        stack.append(bd.pop())
    elif bd[-1] < stack[-1]:
        sumone += len(stack)
        stack.append(bd.pop())
    else:
        stack.pop()

print(sumone)

 

이해하는데 정말 오래걸린 문제. 로직을 이해하는데도 오래걸렸는데 구현도 도움을 조금 받았다..

이 문제의 핵심은 관리인이 옥상정원을 확인하는 총 수와 옥상정원에서 관리인을 보는 총 수가 같다는 것이다.

즉, 높은 빌딩에서 낮은 빌딩을 볼 때와, 낮은 빌딩에서 높은 빌딩을 확인하는 때가 같다.

새로운 스택을 만들고,

3번을 보는 10번(+1), 7번을 보는 10번(+1), 4번을 보는 7번과 10번(+2), 2번을 보는 12번(+1)을 구했다.

10번에서 3번보기(+1), 10번에서 7번보기(+1), 10번에서 7번 보기와 7번에서 4번보기(+2), 12번에서 2번보기(+1)는 위와 같다.

제출 코드(틀린 코드들)

# state 1
N = int(input())
bd = []
for _ in range(N):
    bd.append(int(input()))

sumone = 0 # 벤치마킹하는 빌딩총합
for i in range(N-1):
    for j in range(i+1, N):
        if bd[i] <= bd[j]:
            break
        if bd[i] > bd[j]:
            sumone += 1

print(sumone)

그리디하게 풀었던 첫번째 풀이, 냅다 완전탐색을 했더니 시간초과가 났다.

 

#state 2
from collections import deque

N = int(input())
bd = deque()
for _ in range(N):
    bd.append(int(input()))
    
st = []
sumone = 0
while bd:
    while True:
        if not st:
            if bd:
                st.append(bd.popleft())
            else:
                break
        elif bd[0] < st[-1]:
            st.append(bd.popleft())
            sumone += len(st) - 1
            break
        else:
            st.pop()
            break

print(sumone)

덱을 이용해서 직관적으로 이해하기 쉽게 짜보려했으나 IndexError가 났다.