백준 6198 - 옥상 정원 꾸미기 (Python)

도시에는 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)

출력

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

예제 입력 1 

6
10
3
7
4
12
2

예제 출력 1

5

 

 

---

 

 

import sys
def garden():
    n = int(input())
    arr = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
    stack = []
    answer = 0
    for i in range(n):
        for j in range(len(stack)-1, -1, -1):
            if stack[j] > arr[i]: # 앞 번호의 건물 높이가 현재의 건물 높이보다 높을 경우
                answer += 1
            else:
                stack.pop(j)
        stack.append(arr[i]) # 현재 인덱스 번호의 건물 높이를 stack에 넣어준다. 
    print(answer)
    
if __name__ == "__main__":
    garden()

 

1. stack append : [10]
2. stack[j] = 10 > arr[i] = 3 따라서 answer + 1 그리고 stack append : [10, 3]
3. stack 값 중 뒤에 값 3 < arr 값 7 따라서 stack pop : [10] 
    stack 값 10 > arr 7 따라서 answer + 1 그리고 stack append : [10, 7]
4. 7 > 4 따라서 answer + 1
   10 > 4 따라서 answer + 1 그리고 stack append : [10, 7, 4]
5. 4 < 12 따라서 stack pop :[10, 7]
    7 < 12 따라서 stack pop :[10]
   10 < 12 따라서 stack pop :[]  그리고 stack append : [12]
6. 12 > 2 따라서 answer + 1 그리고 stack append : [12, 2]
7. answer 출력

 

이중 포문이라 불안했지만.... 

역시나 시간 초과.... 너무 어렵다.... 

sys를 이용하면 입력이 빠르다고 해서 바꾸고, pypy3이 속도가 더 빠르다고 해서 제출해 봤지만.... 시간 초과

내용을 바꿔야 한다는 건데... 정말 머리가 안 돌아간다아아아

 

결국 풀이를 찾아보았다. 스택의 길이를 이용하는 방법

스택에 입력되는 값과 순서는 같지만 answer 을 계산하는 방법에서 for 문을 돌리지 않고 stack의 길이로 구하는 방법이 있었다. 

stack append 를 진행한 뒤 스택의 길이에서 1을 뺀 수만큼 다른 건물의 옥상을 볼 수 있다.

위의 stack append 결과를 모아보면

[10] : len(stack) - 1 = 0 

[10, 3] : 높이가 10인 건물에서 높이가 3인 건물의 옥상 보기 가능 : 1 == len(stack) - 1

[10, 7] : 높이가 10인 건물에서 높이가 7인 건물의 옥상 보기 가능 : 1 == len(stack) - 1

[10, 7, 4] : 높이가 10인 건물이 높이가 7인 건물은 이미 전 단계에서 확인했고, 높이가 10인 건물과 7인 건물에서 높이가 4인 건물의 옥상 보기 가능 : 2 == len(stack) - 1 

[12] : 하나라 볼 수 있는 옥상 없음

[12, 2] : 12에서 2 확인 가능 : 1 == len(stack) - 1

따라서 1 + 1 + 2 + 1 = 5

 

import sys
def garden():
    n = int(input())
    arr = [int(sys.stdin.readline().rstrip()) for _ in range(n)]
    stack = []
    answer = 0
    for i in arr:
        while stack and stack[-1] <= i:
            stack.pop()
        stack.append(i)
        answer += len(stack) - 1
    print(answer)

    
if __name__ == "__main__":
    garden()