백준 3015번 오아시스 재결합

문제

오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.

이 역사적인 순간을 맞이하기 위해 줄에서서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해 졌다.

두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.

줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)

둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다.

사람들이 서 있는 순서대로 입력이 주어진다.

출력

서로 볼 수 있는 쌍의 수를 출력한다.

 

 

stack을 활용해서 푸는데

자신 보다 키가 큰 사람이 온다면 자신은 더이상 다른 사람과 짝을 이룰수 없기 때문에 pop()

만약 자신과 같은 키가 온다면 자신은 다른 사람과 짝을 이룰 수 있음. 따라서 pop은 되지 않는다.

그러면 자신 이전에 자신보다 큰 사람들에 대해서 개수를 추출하는 건 어떻게 해야할 까

sta.size()로 하면 안된다.

4 3 2 2 같은 경우 첫 4와 마지막 2는 3 때문에 서로 볼 수 없기 때문..

따라서 pop을 그대로 진행하는 대신 같은 키의 사람은 카운트를 세서 다시 push 해주어야 하는데 시간초과가 걸린다.

그렇다고 현재 sta.size()가 1보다 크다면 그냥 +2 를 해버리는 것도 문제이다. 3이 아니라 4 2 2 2 2 이런 구조였다면

그 앞에 몇개의 같은 개수가 있는지 모르기 때문.

 

<문제의 시간초과 소스> 

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<vector>
using namespace std;

stack<int> sta;


int main()
{
	int N;
	int idx = 0;
	long long ans = 0;



	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;

		int same = 0;
		while (!sta.empty())
		{
			if (sta.top() <= a)
			{
				ans += 1;
				if (sta.top() == a)
				{
					same++;
				}
				sta.pop();
			}
			else
			{
				ans++;
				break;
			}
		}
		if (same)
		{
			for (int i = 0; i <= same; i++)
			{
				sta.push(a);
			}
		}
		else
		{
			sta.push(a);
		}
		
	}
	cout << ans << endl;
}

 

따라서 같다면 기록하기로 결정

 

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<vector>
using namespace std;

stack<pair<int,int> > sta;


int main()
{
	int N;
	int idx = 0;
	long long ans = 0;



	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int a;
		cin >> a;
		pair<int, int> p = { a,1 };
		int same = 0;
		while (!sta.empty())
		{
			if (sta.top().first <= p.first)
			{
				ans += sta.top().second;
				if (sta.top().first == p.first)
				{
					p.second += sta.top().second;
				}
				sta.pop();
			}
			else
			{
				ans++;
				break;
			}
		}
		sta.push(p);
		
	}
	cout << ans << endl;
}