[C++] 3015번 오아시스 재결합 - 자료 구조, 스택

1. 문제

• 두 사람 A, B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 줄에 서 있는 사람의 키가 주어질 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오

<입력>

• - 1 -   기다리는 사람의 수 \(N(1 \leq N \leq 500,000)\)
• - N개의 줄 -   키 \(height(1 \leq height \leq 2^{31})\)

<출력>

• 서로 볼 수 있는 사람의 수

2. 재정의

• 수열이 주어질 때 두 수 사이에 있는 값이 더 작거나 같은 두 수의 순서쌍의 개수를 구하라

3. 해결 방법

• 순차적으로 같거나 내려갈 경우 스택에 추가
• 올라갈 경우 스택에 있는 키를 꺼내는데 같은 키의 개수를 구하자
• 같은 키의 개수를 더하고 스택에 더 있으면 한 번 더 더하자.
• 같은 키C2만 큼 ㄱㄴ하므로 이것도 더하자
• 다 하고 나서 위에서 한 번 더!

4. 실수한 점, 개선할 점

• NC2를 계산할 때 int범위를 넘어갈 수 있다.

 

<코드>

#include <iostream>
#include <stack>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef long long ll;

const int MAX_N = 500001;

// <문제>
// 기다리고 있는 사람의 수 N
int N;
// 사람들의 키 height
int height[MAX_N];

// 사람 번호를 넣는 스택
stack<int> s;
// 서로 볼 수 있는 쌍의 수
ll cnt;

void input() {
    fastio;
    
    cin >> N;
    for(int i=0; i<N; i++)
        cin >> height[i];
}

void solve() {
    int sameCnt, before;
    for(int i=0; i<N; i++) {
        if(s.empty())
            s.push(i);
        else {
            // 전 사람의 키
            before = height[s.top()];
            // 전 사람의 키보다 작거나 같으면 스택에 추가
            if(before >= height[i])
                s.push(i);
            // 전 사람의 키보다 크면 쌍의 수 계산
            else {
                // 스택이 비거나 더 큰 키가 나올 때까지 스택에서 제거하면서 쌍의 수 추가
                sameCnt;
                while(!s.empty()) {
                    sameCnt = 1;
                    before = height[s.top()];
                    if(before >= height[i])
                        break;
                    s.pop();
                    // 같은 키의 수 세기
                    while(!s.empty() && before == height[s.top()]) {
                        s.pop();
                        sameCnt++;
                    }
                    cnt += sameCnt + 1ll * sameCnt * (sameCnt - 1) / 2;
                    if(!s.empty())
                        cnt += sameCnt;
                }
                s.push(i);
            }
        }
    }
    // 스택이 비거나 더 큰 키가 나올 때까지 스택에서 제거하면서 쌍의 수 추가
    while(!s.empty()) {
        before = height[s.top()];
        s.pop();
        sameCnt = 1;
        // 같은 키의 수 세기
        while(!s.empty() && before == height[s.top()]) {
            s.pop();
            sameCnt++;
        }
        cnt += 1ll * sameCnt * (sameCnt - 1) / 2;
        if(!s.empty())
            cnt += sameCnt;
    }
}

int main() {
    input();
    
    solve();
    
    cout << cnt;
    
    return 0;
}

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.