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

📔 문제

---

https://www.acmicpc.net/problem/3015

 

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

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

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

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

입력

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

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

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

출력

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

 

 

👀 문제 풀이

---

 오직 자료구조/스택으로만 풀리는 문제지만 플레티늄5의 문제다 ㄷㄷ 그만큼 스택을 잘 써야한다는 의미... 이전에 풀었던 문제도 마찬가지로 자료구조 문제였음에도 불구하고 플레티늄 5였다 ㅎㅎ;;

 

 

🤔 문제 풀이 Insight

 해당 문제를 해결하기 난해했던 점은, 일단 당장에 스택에 뭘 넣어야 하냐?다. 여기서 포인트인 점은, 그 사람 사이에 키큰 놈이 한명 들어가버리면 뒤쪽에 사람들은 절대 볼 수 없다는 점이다. 그리고, 연달아 같은 키가 나올 경우 애매해질 수 있다는 점이다.

 

 

스택의 top()보다 현재 height가 클 경우에는? 

- 가능한 n 쌍이 늘어난다.  (만약 top()에 여러명일 경우 가능한 쌍이 n쌍 이겠지?)

- top을 빼버린다. 

 

여기서 top을 빼버리는 관점이 대체로 스택으로 풀이되는 문제들에서 필요한 인사이트 중 하나일 것같다.

뺀다는 것은 곧, 뒤에 뭐가 나오든 이 앞쪽은 더이상 가치가 없다는 말이다. 곧, 현재 top보다 큰 사람이 들어온 경우, 다음에 아무리 큰 사람이 들어오든 작은사람이 들어와도 현재의 top을 볼 수가 없다. 즉 더이상 활용 가치가 없어지기에 pop 시켜버리는 것이다. 이것이 메인 포인트였다.

 

 

스택의 top() 현재 height가 작을 경우에는?

- push({height,1}): 1개 추가하면 된다.

- 쌍은 1개 늘어난다. 

 

 

스택의 top()과 같은 height가 들어온 경우에는? 

- top의 second의 개수를 1개 올려주고, 답을 +1해주고, 이전의 개수를 모두 더해줘야한다.

- 자신의 키와 동일한 사람들의 명수 + 남아있는 사람이 더 큰 경우에 마주볼 수 있는 쌍은 오직 1개이기 때문에...

 

 

여튼 이 세가지 원칙을 활용해 코드를 작성하면 문제를 해결할 수 있다. 스택에 top보다 height가 작은 경우에만 담는다는 것이 가장 큰 키 포인트였던 것 같다. 플러스 같은 키의 사람 처리가 난해했던 것 같다.

 

막상... 자료구조로 해결되는 문제인데 사고력이 꽤 요구돼서 플레 5가 된듯?

 

🧑‍💻 최종 코드

---

//
// Created by 정지민 on 8/26/24.
// https://www.acmicpc.net/problem/3015

#include <bits/stdc++.h>

using namespace std;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    stack<pair<int, int>> s; // 키, 개수
    long long ans = 0;
    cin >> n;

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

        // 더 큰게 들어올 경우
        while (!s.empty() && s.top().first < height) {
            ans += s.top().second;
            s.pop();
        }
        if (s.empty()) s.push({height, 1});
        else {
            // 같은게 들어올경우
            if (s.top().first == height) {
                int cur = s.top().second;
                s.pop();

                if(!s.empty()) ans++; // 남아있는 사람이 있는 경우 더 큰 키의 사람과 마주볼 수 있는 쌍은 오직 한 번만 발생하기 때문이다.
                ans += cur;

                s.push({height, cur + 1});
            }
            else { // 더 작은게 들어올 경우
                ans += 1;
                s.push({height, 1});
            }
        }
    }

    cout << ans;
}