BOJ 3015] 오아시스 재결합

[ 1차 시도 ]

- stack에 하나씩 push하다 top()와 해당 숫자를 비교한다.

- 만약 (stack.top() <= arr[i])이면, idx부터 해당 i번까지 (i-j)를 최종값에 더한다.

- 그런데 시간초과가 되어서, 다른 방법을 모색함.

#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <string>
#include <algorithm>


using namespace std;

stack<int> s;
int arr[500001];
int res[500001];
int total = 0;
int n,idx=0;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		
		if(!s.empty() && arr[i] >= s.top()) {
			for (int j = idx; j < i; j++) {
				total+=(i-j);
				
			}
			//cout << "total : " << total << endl;
			idx++;
		}
		
		s.push(arr[i]);
	}

	cout << total;
	
	return 0;
}

 

[ 2차 시도 ] 

- 1차 시도때 for무을 통해 total에 값을 더했기 때문에 시간 초과가 뜬거 같음.

- 도저히 답이 안보여서 블로그 참조 (https://ariz1623.tistory.com/80)

- pair를 first에는 값, second에는 연속으로 몇 명이 왔는지 저장해서 for문 대신 second를 total에 더해 준다.

- 잘 생각해야 될점은 total은 쌍의 갯수를 말한다. 

 

[ 원리 ]

루프를 돌면서 항상 오름차순을 지킨다 (연속명수를 지키기 위해서)

 

{스택이 비어있으면}

- 스택에 {num,1}의 쌍으로 넣는다.

 

{스택이 비어있지 않으면}

    {top == num}

    - top을 백업하고 pop한다.

    - 일단 top의 second(연속명수)를 total에 더한다.

    - 앞에 더 큰 사람이 있으므로 스택이 비지 않으면 total 을 +1한다.

    - 같은 키 끼리는 다음 사람을 볼 수 있으므로, second를 +1해서 다시 push한다.

 

    {top > num}

    - 스택에 {num, 1}로 push한다.

    - 앞에 있는 키 큰사람과 쌍을 맺기 위해 total++ 한다.

 

#include <iostream>
#include <stack>
#include <vector>
#include <set>
#include <string>
#include <algorithm>


using namespace std;

/*
- top == first
- top

*/

stack<pair<long long, long long>> s; // second : 연속으로 몇 명이 오는지
long long total = 0;
long long n;
long long num;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	

	cin >> n;

	for (long long i = 0; i < n; i++) {
		cin >> num;
		
		while (!s.empty() && s.top().first < num) {
			total += (s.top().second);
			s.pop();
		}

		if (!s.empty()) {
			/*
			일단 top의 연속 명수를 total에 더함
			앞에 더 큰 사람이 있으므로 total++
			같은 키들은 앞에 있는 사람 볼 수 있으므로 연속 명수를 더해서 다시 넣어줌
			*/
			if (s.top().first == num) {
				long long topFir = s.top().first;
				long long topSec = s.top().second;
				s.pop();

				total += topSec;

				if (!s.empty())	total++;

				pair<long long, long long> tmp = make_pair(topFir, topSec+1);
				s.push(tmp);
			}
			else {
				s.push({ num,1 });
				total++;
			}
		}
		else {
			s.push({ num,1 });
		}
		
	}

	cout << total;
	
	return 0;
}