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

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

3015번: 오아시스 재결합

 

 문제 설명 

 

1. 줄서있는 사람의 수 N이 주어지고 , N명의 키가 순서대로 주어짐.

2. 각 줄에 서있는 사람들끼리 마주 볼 수있는 경우의 수를 출력.

3. 사람 사이에 자기보다 키가 큰사람이 있으면 마주 볼 수 없음 .

 

 

 알고리즘 

 

1. 처음 사람 은 무조건 stack 에 push

2. 그다음부터 stack 의 top < num  이면 cnt++ 하고 -> 스택 pop 

  -> top 이 empty 이거나 자기보다 클때까지 while문으로 반복후 -> num push

3. top >= num 그럼 cnt++ 하고 top push

4. 이렇게 했을경우 키가 같은사람의 처리가 불 완전 하여 블로그 서칭 . .

 

참고한 블로그  : https://jaimemin.tistory.com/831<- 이분 블로그에는 없는게 없다. 

 

이 블로그에는 키가 같은사람의 수를 pair 로 처리하였다 .코드참고바람 .

 

 코드 

 

#include <iostream>
#include <stack>
using namespace std;
 
typedef long long ll;
 
int main(void)
 
{
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
 
    stack<pair<int, int>> s; //키, 연속 몇 명
 
    ll result = 0;
 
    for (int i = 0; i < N; i++)
    {
        int h;
        cin >> h;
 
        //현재 사람의 키가 스택의 top에 있는 사람보다 크다면
 
        while (!s.empty() && s.top().first < h)
        {
            result += s.top().second;
            s.pop();
        }
 
        if (s.empty())
            s.push({ h, 1 });
 
        else {
            //같은 키의 경우 따로 처리
 
            if (s.top().first == h) {
                pair<int, int> cur = s.top();
                s.pop();
                result += cur.second;
                //스택 내 제일 큰 사람과 쌍을 이룸
                if (!s.empty())
                    result++;
 
                //연속해서 같은 키가 나오므로
                cur.second++;
                s.push(cur);
            }
 
            //더 작은 사람이 왔을 경우
 
            else
            {
                s.push({ h, 1 });
                result++;
            }
        }
    }
    cout << result << "\n";
 
    return 0;
 
}