[Python 파이썬] 백준 6198번 - 옥상 정원 꾸미기

2024년 8월 9일

문제 링크 : 백준 6198번 - 옥상 정원 꾸미기

 

문제

 

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

출력

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

 

알고리즘 분류

• 자료 구조
• 스택

---

 

문제 접근

 

특정 건물의 높이 데이터가 주어질 때마다, 기존에 확인했던 건물의 높이들 중 주어진 높이보다 같거나 낮은 건물들의 데이터를 지속적으로 삭제해주며 진행해야 할 것 같아 스택 자료구조를 활용하는 문제임을 깨달았다.

 

또한, N이 최대 80,000개이고 시간 제한이 1초이므로 브루트포스 방식으로 진행했다간 O(N^2)의 시간복잡도로 시간초과가 날 것 같다는 점 또한 스택을 활용해야겠다는 나의 추측에 힘을 실어주었다.

 

스택을 활용해 문제를 풀이하는 방식은 밑의 입력 예제를 통해 자세히 설명하겠다.

---

입력 예제

 

6
10
3
7
4
12
2

 

초기 세팅 및 1번째 건물 높이 비교

 

now_height는 현재 주어진 건물의 높이이며, stack은 now_height가 주어질 때마다 비교해보려는 건물의 높이들이다.

can_check는 현재 주어진 건물의 옥상을 볼 수 있는 건물들의 개수이며 이는 현재 stack의 길이와 동일하다.

result는 각 건물들이 다른 건물의 옥상을 볼 수 있는 총 개수로 이 문제에서 원하는 해답을 담을 변수이다.

 

초기 stack은 비어있기 때문에 현재 건물을 볼 건물 자체가 없어 result를 증가시키는 연산을 진행하지 못한다.

특별한 연산 없이 stack에 now_height를 append해주고, 스택에 요소가 하나 추가되었으므로 can_check를 1 증가시킨다.

 

2번째 건물 높이 비교

 

now_height가 3이다. stack의 마지막 요소를 보니 now_height보다 큰 수 이므로 stack의 건물은 현재 건물의 옥상을 볼 수 있다. 그러므로 stack의 요소를 pop하는 연산은 진행하지 않는다.

 

현재 건물의 옥상을 볼 수 있는 건물의 개수는 can_check에 담겨 있다. 그러므로 result의 값을 can_check 만큼 증가시켜주고, stack에 now_height를 append하고 can_check를 1 증가시킨다.

 

3번째 건물 높이 비교

 

now_height가 7이다. stack의 마지막 요소를 보니 now_height보다 작으므로, stack의 마지막 높이 정보를 가진 건물은 현재 건물의 옥상을 볼 수 없고, 그 이후에 오는 모든 건물들의 옥상을 볼 수 없다. 

그러므로 stack의 마지막 요소를 pop해주고, can_check의 값을 1 감소시켜준다.

 

 

삭제 연산 이후, stack의 마지막 요소는 now_height보다 크므로, 현재 stack의 건물들은 현재 건물의 옥상을 모두 볼 수 있다. 그러므로 result의 값을 can_check만큼 증가시켜주고 stack에 now_height를 append 해준다. 또한 can_check 값을 1 증가시켜준다.

 

4번째 건물 높이 비교

 

now_height가 4이다. stack의 마지막 요소보다 작으므로 stack에 있는 모든 건물들은 현재 건물의 옥상을 볼 수 있다.

그러므로 result를 can_check 만큼 증가시켜주고, stack에 now_height를 append 후 can_check 값을 1 증가시킨다.

 

 

5번째 건물 높이 비교

 

 

now_height가 12이다. stack의 마지막 요소보다 크므로 stack의 마지막 요소를 pop해주고 can_check를 1 감소시켜준다

이후 stack의 마지막 요소 또한 작으므로 pop 연산 후, can_check를 1 감소시켜준다. 이후 또한 동일하게 작은 값이므로 pop 연산은 총 3번, can_check 값은 총 3 만큼 감소시키게 된다.

 

 

이후, result의 값을 can_check 만큼 증가시켜준다. 하지만 can_check의 값이 0이라 result의 값은 변하지 않는다.

이는 현재 건물의 옥상을 볼 수 있는 건물이 존재하지 않는다는 의미와 같으며, 이는 문제에서 요하는 바와 일치한다.

 

stack에 now_height를 append하고 can_check를 1 만큼 증가시켜준다.

 

6번째 건물 높이 비교

 

 

now_height가 2이다. stack의 마지막 요소보다 작으므로 현재 stack의 건물은 해당 건물의 옥상을 볼 수 있다.

result의 값을 can_check 만큼 증가시켜주고, stack에 now_height를 append 후 can_check를 1 만큼 증가시켜준다.

 

 

로직 종료

 

 

모든 건물을 순회하여 로직이 끝났으므로 최종 result 값인 5가 정답이 된다.

 

출력 예제

 

5

 

 

---

전체 코드

 

# 6198
import sys
input = sys.stdin.readline

if __name__ == "__main__":
    N = int(input())
    result = 0
    # 스택의 길이(특정 높이의 건물을 볼 수 있는 다른 건물들의 개수)를 담아낼 변수
    can_check = 0
    stack = []
    for _ in range(N):
        now_height = int(input())
        while stack and stack[-1] <= now_height:
            stack.pop()
            can_check -= 1
        # 현재 높이의 건물 옥상을 볼 수 있는 건물들의 개수를 result에 합산
        result += can_check
        # 해당 높이의 건물을 stack에 append
        stack.append(now_height)
        can_check += 1

    print(result)

 

---

풀이 후기

 

문제 자체의 내용도 스택을 사용하는 재미있는 문제였지만, 이보다, sys.stdin.readline와 input의 입력 속도 차이를 느낀 문제였다.

 

위 : input(), 아래 : sys.stdin.readline()

 

최대 80,000줄의 입력데이터를 받게되다보니, 두 입력함수의 차이를 확실하게 느낄 수 있었다.