문제
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 - 탑 2493 참고
조건
1. 자기보다 뒤에 있는 건물
2. 자기보다 키가 낮은 건물
두가지 조건을 만족하는 건물의 개수의 합
building.push({1000000001, 0}); //탑 높이제한 1,000,000,000
for(int i=1; i<=n; i++){
int height;
cin >> height;
//현재 스택에 들어있는 top이 입력받은 빌딩의 높이보다 낮으면
while(building.top().first < height)
building.pop();
cout << building.top().second<<" "; //0
building.push({height, i});
}입력 예제 : 10 3 7 4 12 2 일 때 코드 수행 과정
1. 10일때 스택에 아무것도 없으므로 그냥 push
-
3 일때 top=10 > 3이므로 push
-
7 일때 top=3 < 7 이므로 pop()
- top=10 < height=7이므로 while문 빠져나와서
-> 해당 코드가 뭘 의미하는가??
작성중인 코드
#include <bits/stdc++.h>
using namespace std;
int main (void){
ios::sync_with_stdio(0);
cin.tie(0);
//1. n개 입력받기
int n;
cin >> n;
//2. 빌딩 높이 , 관리인 번호를 저장하는 pair 만들기
//pair<빌딩 높이, 관리인 번호>
stack<pair<int, int>> building;
int ans=0;
for(int i=1; i<=n; i++){
int height;
cin >> height;
//현재 스택에 들어있는 top이 입력받은 빌딩의 높이보다 높으면
//10 3 7 4 12 2
while(building.top().first < height && !building.empty())
building.pop();
ans +=
cout << building.top().second<<" "; //0
building.push({height, i});
}
return 0;
}
하나의 탑을 수신받을 수 있는 탑이 오직 하나였던 탑의 문제와는 살짝 다르다.
풀이 2
-
자기보다 뒤에 있는 건물
-
자기보다 키가 낮은 건물
둘을 만족하는 건물 개수의 합을 구하시오. -
나보다 키가 큰 애(옥상 정원을 볼 수 없는 애)는 pop
-
나보다 키가 작은 애의 개수 ++
-
내 키와 idx를 stack에 저장
#include <bits/stdc++.h>
using namespace std;
int N;
stack<int> tower;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
int sum=0;
for (int i = 1; i <= N; i++) {
int height;
cin >> height;
while (tower.top() <= height && !tower.empty()) {
tower.pop();
sum++; //이 부분 틀림
}
tower.push(height);
}
}풀이 3 - 정답 코드
#include <bits/stdc++.h>
using namespace std;
int N;
stack<int> tower;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
long long sum=0;
for (int i = 1; i <= N; i++) {
int height;
cin >> height;
while (!tower.empty() && tower.top() <= height) { // && 앞뒤 순서 바뀌면 안됨
tower.pop();
}
sum += tower.size();
tower.push(height);
}
cout << sum;
}참고
