[백준/파이썬][Gold V] 옥상 정원 꾸미기 - 6198

[Gold V] 옥상 정원 꾸미기 - 6198

문제 링크

성능 요약

메모리: 116284 KB, 시간: 144 ms

분류

자료 구조, 스택

제출 일자

2024년 12월 27일 20:08:39

문제 설명

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

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

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

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번째 줄까지 각 빌딩의 높이가 h_i 입력된다. (1 ≤ h_i ≤ 1,000,000,000)

출력

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

풀이

N = int(input())
arr = [int(input()) for _ in range(N)]

stack = []
res = []
for i in range(N - 1, -1, -1) :         # 빌딩을 뒤에서부터 순회
    cnt = 0                             # 현재 빌딩에서 볼 수 있는 빌딩 개수
    for j in range(len(stack)) :        # 스택의 빌딩들을 순회
        if stack[-1][0] < arr[i] :      # 스택의 마지막 빌딩이 현재 빌딩 보다 낮으면
            cnt += stack[-1][1] + 1     # 해당 빌딩에서 볼 수 있는 빌딩 개수 + 1 증가
            stack.pop()                 # 스택에서 제거
        else :                          # 스택의 마지막 빌딩이 현재 빌딩보다 높거나 같으면
            stack.append((arr[i], cnt)) # 현재 빌딩과 볼 수 있는 개수를 스택에 추가
            break

    if not stack :                      # 스택이 비어 있다면
        stack.append((arr[i], cnt))     # 현재 빌딩과 볼 수 있는 개수를 추가
    res.append(cnt)                     # 현재 빌딩에서 볼 수 있는 빌딩 수 저장

print(sum(res))                         # 리스트의 합 출력

주요 논리와 동작 방식

1. 뒤에서부터 순회

for i in range(N - 1, -1, -1) :         # 빌딩을 뒤에서부터 순회
    cnt = 0                             # 현재 빌딩에서 볼 수 있는 빌딩 개수

• for i in range(N - 1, -1, -1):
  • 빌딩 배열을 역순으로 탐색. 뒤에서부터 탐색함으로써 현재 빌딩보다 오른쪽에 있는 빌딩만 처리하면 된다.

---

2. 스택 활용

if not stack :                      # 스택이 비어 있다면
    stack.append((arr[i], cnt))     # 현재 빌딩과 볼 수 있는 개수를 추가

• stack은 다음 두 가지 정보를 담고 있다.:
  1. 빌딩의 높이 (stack[-1][0])
  2. 해당 빌딩에서 볼 수 있는 빌딩의 개수 (stack[-1][1])
• 스택을 사용해 현재 빌딩보다 낮은 빌딩들을 제거하면서 볼 수 있는 빌딩의 수를 효율적으로 계산.

---

3. 빌딩 비교

for i in range(N - 1, -1, -1) :         # 빌딩을 뒤에서부터 순회
    cnt = 0                             # 현재 빌딩에서 볼 수 있는 빌딩 개수
    for j in range(len(stack)) :        # 스택의 빌딩들을 순회
        if stack[-1][0] < arr[i] :      # 스택의 마지막 빌딩이 현재 빌딩 보다 낮으면
            cnt += stack[-1][1] + 1     # 해당 빌딩에서 볼 수 있는 빌딩 개수 + 1 증가
            stack.pop()                 # 스택에서 제거
        else :                          # 스택의 마지막 빌딩이 현재 빌딩보다 높거나 같으면
            stack.append((arr[i], cnt)) # 현재 빌딩과 볼 수 있는 개수를 스택에 추가
            break

• if stack[-1][0] < arr[i]:
  • 현재 빌딩 arr[i]보다 스택의 마지막 빌딩(stack[-1][0])이 낮으면:
    1. 해당 빌딩과 그 빌딩에서 볼 수 있는 빌딩 개수를 합산 (cnt += stack[-1][1] + 1).
    2. 스택에서 제거 (stack.pop()).
  • 이 과정을 반복해 현재 빌딩보다 낮은 빌딩들을 모두 제거.
• elif stack[-1][0] >= arr[i]:
  • 현재 빌딩보다 높은 빌딩이 나오면:
    1. 현재 빌딩의 높이와 볼 수 있는 빌딩 수를 스택에 추가 (stack.append([arr[i], cnt])).
    2. 반복문을 종료 (break).

---

4. 스택 비어있는 경우

if not stack :                      # 스택이 비어 있다면
    stack.append((arr[i], cnt))     # 현재 빌딩과 볼 수 있는 개수를 추가

• if not stack :
  • 스택이 비어 있다면 현재 빌딩을 스택에 추가.
  • 이 경우 현재 빌딩에서 볼 수 있는 빌딩은 없으므로 cnt는 0.

---

5. 결과 저장

    res.append(cnt)                     # 현재 빌딩에서 볼 수 있는 빌딩 수 저장

print(sum(res))                         # 리스트의 합 출력

• res.append(cnt)
  • 각 빌딩에서 볼 수 있는 빌딩 수를 결과 리스트 res에 저장.

---

6. 최종 합 계산

• sum(res)
  
  • res 리스트에 저장된 각 빌딩에서 볼 수 있는 빌딩의 개수를 모두 더해 최종 결과를 구한다.

---

시간 복잡도 분석

1. 스택 연산
   • 스택에 빌딩을 추가하거나 제거하는 연산은 평균적으로 O(1).
   • 모든 빌딩이 한 번씩 스택에 추가되고 한 번씩 제거되므로 스택 관련 연산은 O(N).
2. 전체 반복
   • 빌딩 배열을 한 번 순회하므로 O(N).
3. 총 시간 복잡도
   • 평균적으로 O(N), 최악의 경우에도 O(N^2) (스택 연산이 반복적으로 발생할 때).

---

핵심 아이디어 요약

• 현재 빌딩에서 오른쪽에 있는 빌딩만 고려하기 위해 스택을 사용하여 효율적으로 처리.
• 낮은 빌딩들을 제거하면서 볼 수 있는 빌딩 개수를 합산하는 방식으로 계산량을 줄임.
• 빌딩 배열을 역순으로 탐색하며, 스택을 활용해 중복된 비교를 방지.

---

주요 포인트

• 이 코드는 스택을 사용하여 효율적으로 빌딩 비교 문제를 해결한 예이다.
• 반복문 내부에서 스택의 상태와 연산을 잘 이해하면 비슷한 유형의 문제를 해결하는 데 도움이 된다.