문제 출처

1. 문제설명

  • 공연에 N명이 한 줄로 서서 기다리고 있다.
  • 두 사람 A와 B가 서로 볼 수 있으려면,
    • 두 사람 사이에 A, B보다 키가 큰 사람이 없어야한다.
  • 줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하라



2. 알고리즘 설계

  • 자료구조 스택 문제이다.
  • 입력받은 숫자와 누적된 쌍의 개수를 함께 저장한다.



3. 로직

  • pair 구조에 높이와 개수를 함께 저장한다.
    • 여기서 개수는, 높이에 대한 쌍의 개수이다.
  • 만약, 스택의 top이 입력받은 높이보다 작거나 같다면,
    • top의 개수. 즉, 누적된 쌍의 개수를 정답에 더한다.
    • 만약 같다면, 이후에 저장될 개수에는 top의 개수를 더한다.
      • 문제를 보면 키가 큰 사람만이 조건에 해당되기 때문이다.
  • 스택이 비어있지 않다면, 현재 top이 입력받은 높이보다 크다는 의미이므로,
  • 정답값을 +1 해준다.



4. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	stack<pii> st;
	int n;
	long long ans = 0;

	cin >> n;
	while (n--) {
		int h, cnt = 1;
		cin >> h;

		while (!st.empty() && st.top().first <= h) {
			ans += st.top().second;
			if (st.top().first == h) cnt += st.top().second;
			st.pop();
		}

		if (!st.empty()) ans++;
		st.push({ h, cnt });
	}
	
	cout << ans;
	return 0;
}



5. 소감

  • 문제의 난이도가 플레티넘5로 꽤 높은 편이다.
  • 그에 비해 코드는 간결한 것을 볼 수 있는데,
  • 아마도 pair 자료형과 스택을 적절히 잘 활용해야하기 때문인 거 같다.