문제 설명
두 사람 사이에 두 사람보다 키가 큰 사람이 없으면 서로를 볼 수 있습니다.
서로 볼 수 있는 쌍의 수를 구하는 문제입니다.
풀이
모든 쌍을 비교해서 보면 편하겠지만 O(N^2)이므로 시간을 더 줄여야 합니다.
키가 X인 사람이 있다면 그 사람의 오른쪽에 있는 사람은 그 사람의 왼쪽에 있는 사람보다 작은 사람들은 볼수 없습니다.
오른쪽에 있는 사람들 중 X보다 작은 사람도 볼 수 없습니다.
이를 이용하여 왼쪽에 있는 사람들 중 볼 수 있는 사람들만 구하겠습니다.
왼쪽 사람들 중 X보다 작은 사람이 있다면 그 사람은 그 다음 사람부터 볼 수 없으니 찾아서 체크해줘야 하는데 일반 반복문으로 할 경우에 O(N^2)이 되므로 스택을 사용하여 다음 사람부터 볼 수 있는 사람들을 스택에 저장해주겠습니다.
그럼 스택에 있는 사람들은 키 기준으로 내림차순으로 쌓여있습니다.
X보다 작은 사람들은 볼 수 있으니 그 키를 가진 사람의 수를 더해주고 스택에서 pop을 합니다.
그렇게 X보다 작은 사람들을 다 pop하고 스택에 남아있는 사람이 있으면 사이에 X보다 작은 사람이 없으므로 +1을 해주고 스택에 넣어줍니다.
그렇게 하면 볼 수 있는 모든 쌍을 구할 수 있는데 키가 같은 사람이 나올 때만 사람 수를 잘 처리하여 저장하면 별 다른 반례가 없을 것 같습니다.
N = 7 (2,4,1,2,2,5,1) 예제로 스택 push, pop 과정을 보여 드리겠습니다.
(2) 스택이 비어있으니 별 다른 처리를 없이 push를 해줍니다.
(4) 스택에 4보다 작은 값이 있으니 pop을 해주고 사람 수를 더해줍니다.
(1) 1보다 작은 값이 스택에 없으니 pop을 하지 않고 스택에 남아있는 수가 있으니 1을 더합니다. (4를 볼 수 있습니다.)
(2) 1이 2보다 작기 때문에 pop을 해주고 사람 수를 더해줍니다. 스택에 4가 남아있기 때문에 1을 더합니다.
(2) 2와 같은 수가 있기 때문에 pop을 하고 더한 후에 사람 수를 +1하여 스택에 넣어줍니다. 스택에 넣기 전 4가 있으니 1을 더합니다.
(5) 스택에 있는 값들이 다 작기 때문에 사람 수를 더해주고 push를 합니다.
(1) 스택에 1보다 작은 값이 없으므로 pop을 하지 않고 스택에 5가 남아있으므로 1을 더하고 push를 합니다.
모든 과정이 끝났습니다. 답을 출력하시면 됩니다!!
소스 코드
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i, a, b) for(int i=a;i<=b;i++)
#define pii pair <int,int>
#define fs first
#define sd second
#define ep emplace
#define ll long long
using namespace std;
int main() {
FIO;
int n; cin >> n;
stack <pii> s;
ll ans = 0;
FOR(i, 1, n) {
int x; cin >> x;
while (s.size() && s.top().fs < x) {
ans += s.top().sd;
s.pop();
}
int val = 1;
if (s.size() && s.top().fs == x) {
val += s.top().sd;
ans += s.top().sd;
s.pop();
}
if(s.size()) ans++;
s.ep(x, val);
}
cout << ans << '\n';
return 0;
}