백준 - 3015번 오아시스 재결합

문제

두 사람 A와 B 사이에 A또는 B보다 키가 큰 사람이 없을 때 서로 볼 수 있다면
줄에 서있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성해라

생각

시간 초과

입력이 500,000으로 엄청 크게 주어지니까,
이중 for문으로 탐색을 하면 시간 초과가 나올 것 같았다

그래서 제일 키가 큰 사람을 찾아서 왼쪽 오른쪽 나눠서 구해볼까.. 했는데
이것도 모든 곳을 돌아야하는 건 똑같더라..! 그래서 시간 초과..

그치만 좋은 아이디어가 떠오르지 않았었다!
이게 어떻게 스택/큐 문제야..!!?!?

구글링

구글링을 했다 이 문제는 2가지가 어려운 것 같다

1. 어떻게 stack을 사용해서 문제를 풀 수 있는지
2. 중복된 키가 들어왔을 때는 어떻게 해야하는지

나는 1, 2가 모두 적용된 코드를 보았을 때 바로 이해하기 어려웠어서
나눠서 설명을 하려고 한다

키가 중복되지 않은 경우

들어오는 입력의 맨 왼쪽에서부터 오른쪽으로 보면서 (O(n))
서로 매칭이 될 가능성이 있는 애들만 stack에 저장을 한다

즉, 키가 작은 사람이 더 큰 사람들로 둘러쌓이게 되면
더 이상 다른 사람을 볼 수 없으니까 그 작은 사람을 스택에 넣지 않도록!!

이렇게 하면 항상 stack엔 내림차순으로 값이 들어가 있을거에요

ex) 5 3 2 4 1 로 입력이 주어지면

5 push 3 push 2 push (stack엔 5, 3, 2가 저장)

4를 push하려고 보니,
3은 4보다 작아서 더 이상 오른쪽에 들어오는 다른 사람을 볼 수 없음 pop
2은 4보다 작아서 더 이상 오른쪽에 들어오는 다른 사람을 볼 수 없음 pop

4 push (stack엔 5, 4가 저장)

1 push (stack엔 5, 4, 1가 저장)

이렇게 하면 되는구나!! 굉장해!!!

for (int i = 0; i < n; i++) {
    int h;
    cin >> h;

    while (!s.empty()) { //더 이상 작은 값이 없을때까지 while돌면서
        if (s.top() < h) { //새로 들어오는 키보다 작은 값이면 pop()
            result++; //작은 값도 새로 들어오는 키랑 매칭은 됌
            s.pop();
        }
        else { 
            result++; //새로 들어오는 키가 stack top()이랑 매칭
            //내림차순으로 값이 저장되어 있으니까 top()이외에 다른 아이들은 못 봄
            break; //음! 나보다 작은 애 없구만 탈출해서 push하러 가자!
        }
    }
    s.push(h);
}

키가 중복되는 경우

근데 이 문제는 키가 중복되서 들어올 수 잇다

예를들어 스택에 3, 3 이 있는데 3이 새로 들어올 때, 4이 새로 들어올 때 처리를 해줘야한다

사이에 큰 키가 있는 경우에만 못 보는 것이기 때문에
3 3 3 끼리는 서로 다 볼 수 있고
3 3 3 4 일 때 4가 3개의 3을 다 볼 수 있다
(3 3 3 1 일땐 1이 예전이랑 똑같이 top()인 하나만 볼 수있음)

따라서 스택에 어떤 키가 들어있는지와 추가적으로 같은 키가 몇 명 있는지도 저장한다
stack< long long> s; -> stack<pair<long long, long long>> s; //키, 중복된 개수

ex)
top()이 (n, count)라면

n이 들어오면
result에 count만큼을 더해주고(같은 애들끼리 서로 볼 수 있음) pop()
(n, count+1)인 새로운 값을 push()

키가 i (i>n)인 값이 들어오면
result에 count만큼을 더해주고(작은 애들을 다 볼 수 있음) pop()
(i, 1)인 새로운 값을 push()

아래의 코드를 참고해주세여~!!~ (long long 자료형을 써야하는걸 유의해야함)

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

int n;
long long result;
stack<pair<long long, long long>> s; //키, 중복된 개수

int main() {

	cin >> n;

	for (int i = 0; i < n; i++) {
		long long h;
		cin >> h;

		int count = 1;
		while (!s.empty()) {
			if (s.top().first < h) {
				result += s.top().second;
				count = 1;
				s.pop();
			}
			else if (s.top().first == h) {
				result += s.top().second;
				count = s.top().second + 1;
				s.pop();
			}
			else {
				result++;
				break;
			}
		}
		s.push(make_pair(h, count));
	}

	cout << result;

	return 0;
}