[BaekJoon] 3015번 - 오아시스 재결합 [Java][C++]

문제 링크

---

1. 문제 풀이

한 줄로 서 있는 $N$ 명의 사람들에 대해 서로 볼 수 있는 쌍의 수를 구하는 문제로 $N$ 이 최대 $500,000$ 이어서 단순한 브루트 포스 탐색으로는 해결할 수 없다. 해당 문제는 단조 스택을 활용하면 해결할 수 있는데 특정 사람은 자신보다 큰 사람이 등장하기 전까지 가려지지 않은 왼쪽 사람들을 모두 볼 수 있다는 점을 활용하면 된다.

예제 입력 1의 예시는 아래와 같다.

첫 번째 사람인 2는 볼 수 있는 왼쪽 사람이 없다.

다음 사람인 4은 왼쪽의 2를 볼 수 있다.

다음 사람인 1은 왼쪽의 4를 볼 수 있다. 하지만 2는 4에 가려져서 볼 수 없다. 한번 가려지면 이후로도 계속 볼 수 없다.

다음 사람인 2는 왼쪽의 4와 1을 볼 수 있다.

다음 사람인 2는 왼쪽의 4와 2를 볼 수 있다. 하지만 1은 이전의 2에 가려져서 볼 수 없다.

다음 사람인 5는 왼쪽의 4, 2, 2를 볼 수 있다.

마지막 사람인 1은 왼쪽의 1을 볼 수 있다. 5가 나머지 사람들을 모두 가려서 다른 사람은 볼 수 없다.

이렇게 서로 볼 수 있는 10쌍을 구했다.

현재 사람은 이전에 등장한 자신보다 작은 사람을 모두 가리므로 단조 스택을 활용하면 현재 사람이 단조 스택의 맨 앞사람보다 큰 동안 쌍을 맺고 스택에서 제거한 후 삽입하면 된다. 스택에 자신보다 작은 원소를 순서대로 제거한 후 삽입하므로 이 스택은 단조 스택이 된다. 키가 동일할 경우 키와 등장 횟수를 같이 저장하면 최적화를 할 수 있는데 이를 위해 연속으로 등장한 동일 키의 경우 하나로 압축을 해줄 수 있다. 현재 사람에 대해 자신보다 작거나 같은 사람과 모두 쌍을 맺고 자신보다 크면서 왼쪽에 위치한 한명과도 쌍을 맺는 과정을 반복하기 때문에 모든 사람에 대해 쌍을 구할 수 있다.(자신보다 큰 사람이 왼쪽에 여럿이 있어도 그 중 가장 오른쪽 사람과만 쌍을 맺을 수 있다.)

---

2. 코드

1. 풀이 [Java]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Deque<int[]> stack = new ArrayDeque<>();
        long ans = 0;

        int n = Integer.parseInt(br.readLine());
        while (n-- > 0) {
            int x = Integer.parseInt(br.readLine());
            int cnt = 1;

            while (!stack.isEmpty() && stack.peek()[0] < x) {
                ans += stack.pop()[1];
            }

            if (!stack.isEmpty() && stack.peek()[0] == x) {
                int[] top = stack.pop();
                ans += top[1];
                cnt += top[1];
            }

            if (!stack.isEmpty()) ans++;

            stack.push(new int[]{x, cnt});
        }

        System.out.println(ans);
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

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

    stack<pair<int, int>> st;
    long long ans = 0;

    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;
        int cnt = 1;

        while (!st.empty() && st.top().first < x) {
            ans += st.top().second;
            st.pop();
        }

        if (!st.empty() && st.top().first == x) {
            ans += st.top().second;
            cnt += st.top().second;
            st.pop();
        }

        if (!st.empty()) ans++;

        st.push({x, cnt});
    }

    cout << ans;
}

---