백준 8155 c++ "Postering" -PlusUltraCode-

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

 

 [필자 사고]

이 문제는 플래 5에 있는 히스토그램을 한번 풀어봤으면 쉽게 응용하여 풀 수 있는문제이다.

특히 스택을 활용하면 코드길이를 엄청 줄일 수 있다.

아래는 코드의 해설이다.

[코드 해설]

1. 입력 처리

• 입력값 n: 빌딩의 개수.
• 각 빌딩의 정보 (d, h):
  • d: 빌딩의 위치 (문제에서 사용되지 않음).
  • h: 빌딩의 높이.

입력은 한 줄에 하나의 빌딩 정보 (d, h) 형식으로 주어집니다.

---

2. 변수 초기화

• stack<int> heights:
  • 현재 활성화된(유효한) 빌딩 높이를 저장하는 스택입니다.
  • 이 스택은 현재까지 고려된 높이를 관리하여 겹치는 포스터를 줄이는 데 사용됩니다.
• int posters:
  • 필요한 포스터의 수를 저장하는 변수로, 초기값은 0입니다.

---

3. 알고리즘 과정

각 빌딩의 높이를 처리하면서 포스터를 계산합니다.

(1) 스택에서 현재 빌딩의 높이보다 큰 값을 제거

cpp

복사편집

while (!heights.empty() && heights.top() > h) { heights.pop(); }

• 스택의 가장 위에 있는 높이가 현재 빌딩의 높이 h보다 크다면, 스택에서 제거합니다.
• 이는 현재 빌딩에서 이전의 높은 빌딩이 더 이상 영향을 주지 않음을 의미합니다.

(2) 현재 높이가 새로운 포스터가 필요한 경우 처리

cpp

복사편집

if (heights.empty() || heights.top() < h) { posters++; heights.push(h); }

• 스택이 비어있거나, 현재 빌딩의 높이가 스택의 가장 위 높이보다 높으면 새로운 포스터가 필요합니다.
• posters 값을 증가시키고, 현재 높이를 스택에 추가합니다.

---

4. 출력

마지막으로 필요한 포스터의 총 개수를 출력합니다:

cpp

복사편집

cout << posters << endl;

---

5. 코드 핵심 정리

• 스택 사용 이유:
  • 스택은 현재 활성화된 높이를 관리하여 불필요한 높이를 제거하고, 새로운 포스터가 필요한 상황을 빠르게 판단할 수 있게 합니다.
• 효율성:
  • 각 빌딩의 높이는 스택에 한 번 추가되고 한 번 제거되므로, 시간 복잡도는 O(n)입니다.
• 주요 조건:
  • 높이가 감소할 때 스택에서 제거.
  • 높이가 증가할 때 포스터 추가.

[소스 코드]

#include <iostream>
#include <stack>
using namespace std;

int main() {
    int n;
    cin >> n;

    stack<int> heights; 
    int posters = 0;   

    for (int i = 0; i < n; i++) {
        int d, h;
        cin >> d >> h; 

        
        while (!heights.empty() && heights.top() > h) {
            heights.pop();
        }

      
        if (heights.empty() || heights.top() < h) {
            posters++;
            heights.push(h);
        }
    }

    cout << posters << endl;
    return 0;
}