[백준 3015] 오아시스 재결합 (C#, C++) - soo:bak

문제 링크

3015번 - 오아시스 재결합

설명

N명의 사람이 줄을 서 있고 각 사람의 키가 주어지는 상황에서, N (1 ≤ N ≤ 500,000)과 각 사람의 키가 주어질 때, 서로 볼 수 있는 사람 쌍의 개수를 구하는 문제입니다.

두 사람이 서로 볼 수 있으려면, 그들 사이에 있는 모든 사람들의 키가 두 사람의 키보다 작아야 합니다.

접근법

모든 사람 쌍을 직접 확인하면 O(N²) 시간이 걸려 N = 500,000일 때 시간 초과가 발생합니다.

효율적으로 해결하기 위해 각 사람을 순서대로 처리하면서, 그 사람과 볼 수 있는 이전 사람들을 빠르게 찾는 방법을 사용합니다.

핵심 아이디어는 현재까지 처리한 사람들 중에서 “아직 누군가와 쌍을 이룰 가능성이 있는” 사람들만 기억하는 것입니다.

어떤 사람 A보다 뒤에 있으면서 키가 더 큰 사람 B가 나타나면, A는 B보다 뒤의 사람들과는 절대 볼 수 없습니다. B가 가려버리기 때문입니다.

따라서 뒤로 갈수록 키가 작아지거나 같은 사람들만 기억하면 됩니다.

각 사람을 처리할 때:

1. 현재 사람보다 키가 작은 이전 사람들 처리:

• 현재 사람의 키가 더 크므로 서로 볼 수 있습니다
• 이들은 현재 사람 뒤의 사람들과는 볼 수 없으므로 제거합니다
• 제거되는 각 사람(또는 같은 키의 그룹)과 현재 사람이 한 쌍을 이룹니다

2. 현재 사람과 키가 같은 이전 사람들 처리:

• 같은 키끼리는 서로 볼 수 있으므로 모두 쌍을 이룹니다
• 같은 키 그룹을 하나로 묶어 관리하여 효율성을 높입니다
• 이 그룹보다 앞에 더 큰 키가 있다면 그 사람과도 쌍을 이룹니다

3. 현재 사람보다 키가 큰 사람 처리:

• 가장 가까운 더 큰 키의 사람과 한 쌍을 이룹니다
• 그보다 앞의 사람들은 이 큰 키에 가려져 볼 수 없습니다

예를 들어, 키가 [2, 4, 1, 2, 2, 5, 1]인 경우:

• 2: 처음 → 쌍 0개
• 4: 2보다 큼 → 2와 볼 수 있음 → 쌍 +1 (총 1개)
• 1: 4보다 작음 → 4와 볼 수 있음 → 쌍 +1 (총 2개)
• 2: 1보다 큼 → 1과 볼 수 있음, 4와도 볼 수 있음 → 쌍 +2 (총 4개)
• 2: 앞의 2와 같음 → 앞의 2와 볼 수 있음, 4와도 볼 수 있음 → 쌍 +2 (총 6개)
• 5: 2,2,4보다 큼 → 모두와 볼 수 있음 → 쌍 +3 (총 9개)
• 1: 5보다 작음 → 5와 볼 수 있음 → 쌍 +1 (총 10개)

같은 키의 사람들을 그룹으로 묶어 (키, 연속 개수)로 관리하면, 각 사람을 한 번씩만 처리하므로 O(N) 시간에 해결할 수 있습니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      var stack = new Stack<(int height, long count)>();
      var pairs = 0L;

      for (var i = 0; i < n; i++) {
        var height = int.Parse(Console.ReadLine()!);

        while (stack.Count > 0 && stack.Peek().height < height) {
          pairs += stack.Pop().count;
        }

        if (stack.Count == 0) {
          stack.Push((height, 1));
          continue;
        }

        if (stack.Peek().height == height) {
          var top = stack.Pop();
          pairs += top.count;
          if (stack.Count > 0) pairs++;
          stack.Push((height, top.count + 1));
        } else {
          pairs++;
          stack.Push((height, 1));
        }
      }

      Console.WriteLine(pairs);
    }
  }
}

C++

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

typedef long long ll;
typedef pair<int, ll> pil;
typedef stack<pil> spil;

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

  int n; cin >> n;
  spil st;
  ll pairs = 0;

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

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

    if (st.empty()) {
      st.push({height, 1});
      continue;
    }

    if (st.top().first == height) {
      auto top = st.top();
      st.pop();
      pairs += top.second;
      if (!st.empty()) pairs++;
      st.push({height, top.second + 1});
    } else {
      pairs++;
      st.push({height, 1});
    }
  }

  cout << pairs << "\n";
  
  return 0;
}