[백준 6198번] 옥상 정원 꾸미기 (Python)

> 파이썬, 자료 구조, 스택

 

 

 

 

 

📖 문제 : 옥상 정원 꾸미기 (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

 

 

내 코드

N = int(input())

building = list(int(input()) for _ in range(N))
stack = []
result = 0

stack.append(building[0])

for i in range(1, N):

    print(stack)
    while True:
        if len(stack) > 0 and stack[-1] <= building[i]:
            stack.pop()
        else:
            break

    print(stack)
    result += len(stack)
    stack.append(building[i])

print(result)

 

 

 

Point ! ⭐️ 

• 이 문제는요 !!! 일단 다른 분 코드 참고했고요 !!! 스택문제라서, 리스트를 거꾸로 읽어가면서 자기보다 큰애가 나오면 뭐 그런식으로 빌딩수를 남겨서 스택의 길이를 결과값에 계속 더해주는 방식으로 해야하는 줄 알았는데, 그렇게 되면 생각해야하는 경우의 수도 많고, 답은 일단 틀렸더라구요 !
  
  완전 생각의 전환이 필요한 문제였어요.. 일단 이거 푸신 분들은 머리가 상당히 좋으신 것 같슴다 😭
  
  그냥 리스트를 앞에서 부터 읽어주면서 내림차순으로 만들어주고, 그 길이를 결과값에 더해주면 되는 문제였습니다. 
  
  
  어려웡 ... 골드 5인데 이럴 때마다 벽이 느껴지네요 ㅎㅎㅎ
  그럴수록 더 열심히 해야겠어요 빠샤 !!!!!!!!!!1

 

 

 

 

 

 

백준 

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

6198번: 옥상 정원 꾸미기