[백준]Baekjoon3015(스택)

문제링크 : https://www.acmicpc.net/problem/3015

풀이

정답률이 22%대로 낮은편이며 아주 골치아픈 문제이다.

일단 이 문제를 풀기위한 가장 깔끔한 방법은 새로운 사람이 줄을 설 때마다

처리해주는 식으로 문제를 푸는 것이다.

예를들어 2 1 4 순으로 줄을 서 있다고 해보자

맨 첫사람의 키인 2는 일단 스택에 넣어주고

키가 1인 다음사람을 처리해준다. 앞사람보다 키가 작아 앞사람이 다음사람을 보는데 문제가 

없으므로 (1,2)의 짝만 나오기 때문에 최종답에 1을 더해준다.

키가 4인 다음 사람을 처리해 줄 때 키가 1인 사람은 더이상 사람을 볼 수 없으므로 (1,4)인 케이스,

그리고 pop을 해준뒤 키가 2인 사람도 더 이 사람보다 키가 작기 때문에 (4,2)인 케이스를 더해서

최종답은 3이된다. 

이렇게만 된다면 쉬운 문제겠지만 이 문제에서 골치아픈 경우는 키가 같은 사람이 차례로 섰을 

경우이다. 그 경우에 대해 코드와 함께 설명해보겠다.

일단 초기화 과정은 다음과같이 이루어진다.

        int n;
	scanf("%d", &n); //총 줄을 서는 사람의 수
	stack<pair<int, int>> stk; //스택의 첫번 째 인자는 사람의 키, 두번째 인자는 같은 키 누적
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]); //초기화
	long long answer = 0; //최종 정답
	stk.push(make_pair(arr[0], 1)); //맨 첫번째 사람 스택에 push
	int x; //같은 키 누적을 위해 사용하는 변수

일단 스택을 왜 pair형태로 선언하냐에 대해서 설명하자면

키가 같은 사람이 연속해서 줄을 서는 상황에 대해서 해결하기 위함이다. 

예를들어 줄을 8 6 6 6 6 5 7  와 같이 섰다면 스택의 특성상 pop을 하면서 짝의 수를 세기 떄문에

줄지어 있는 6의 짝을 세어주기 어렵다.

그렇기 때문에 아래 코드와 같이 만약 스택에 있는수와 같은 수가 들어온다면 

스택에서 pop하면서 해당 숫자와 두번 째 인자를 제거해주고 두번쨰 인자에 1을 더한 값을

새로 스택에 다시 넣는 것이다. 

그러니까 6 6 6 6 의 경우

처음엔 (6,1)이 push 그 다음 6이 들어오면 answer에 1이 더해지고 원래것이 pop되면서

(6,2)가 push 그 다음 6이 들어오면 answer에 2가 더해지고 (6,3)이 push되는 식이다.

이렇게 하면 키가 같은 사람들의 짝도 충분히 잘 반영할 수 있다.

#include <iostream>
#include <stack>

using namespace std;

int arr[500000];

int main()
{
	int n;
	scanf("%d", &n); //총 줄을 서는 사람의 수
	stack<pair<int, int>> stk; //스택의 첫번 째 인자는 사람의 키, 두번째 인자는 같은 키 누적
	for (int i = 0; i < n; i++) scanf("%d", &arr[i]); //초기화
	long long answer = 0; //최종 정답
	stk.push(make_pair(arr[0], 1)); //맨 첫번째 사람 스택에 push
	int x; //같은 키 누적을 위해 사용하는 변수
	for (int i = 1; i < n; i++)
	{
		x = 1;
		while (!stk.empty() && arr[i] >= stk.top().first) {
			if (arr[i] > stk.top().first) {
				answer += stk.top().second;
				stk.pop();
				x = 1;
			}
			else if (arr[i] == stk.top().first) {
				answer += stk.top().second;
				x = stk.top().second + 1;
				stk.pop();
			}
		}
		if (!stk.empty()) answer++;
		stk.push(make_pair(arr[i], x));
	}
	printf("%lld\n", answer);
}