백준 오아시스 재결합 - 3015 풀이(c++)

문제 링크

성능 요약

메모리: 10420 KB, 시간: 68 ms

분류

자료 구조, 스택

제출 일자

2025년 3월 4일 17:16:48

문제 설명

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

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

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

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

입력

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

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

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

출력

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

 

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

using namespace std;

long long N, iResult = 0;
string strInput;

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

    cin >> N;

    int iInput;
    stack<pair<long long, long long>> st;
    for (int i = 0; i < N; ++i)
    {
        cin >> iInput;
        int iCount = 1;
        while (st.size() && st.top().first <= iInput)
        {
            iResult += st.top().second;
            if (st.top().first == iInput)
                iCount = st.top().second + 1;
            else
                iCount = 1;

            st.pop();
        }
        if (st.size())
            ++iResult;

        st.push({ iInput , iCount});
    }

    cout << iResult;
    return 0;
}

 

stack 과 여러 경우의 수를 조건을 확인해 풀이

 

게시판을 보고 알았지만 참고로 카운팅이 int 수를 넘어가기 때문에 long long 자료형을 써야한다.