Bel's log

풀이

처음엔 간단하게 중간값부터 포인터 두 개를 사용해서 조합을 만들려고 했다. 정렬해서 중간 값 좌우를 보면 간단히 조합의 개수를 셀 수 있는데다가 모든 조합을 구하는 것이 아니라 조합의 개수를 찾는 것이기 때문에 중간 값의 좌우 개수를 곱해주면 되기 때문이다.

다만 간과한 것이 중간 값이 다양하게 나올 때마다 중간에 있는 중간 값을 찾아줘야 하는데 이 경우 find 함수를 쓰게 되면 시간복잡도가 O(n) 이다. 거기에 중간 값이 q 번만큼 나오기 때문에 최종 시간 복잡도는
정렬 + (find * 중간값 input) = O(n log n + n * q) 가 된다. n의 최대는 5만, q의 최대는 20만이기 때문에 곱하면 100억이 된다...

그래서 시간 복잡도를 줄이기 위해 값들과 함께 인덱스를 미리 unordered_map에 저장하는 방식을 사용했습니다. 해당 방식을 사용하면 find와 다르게 주어지는 중간 값으로 바로 인덱스를 찾을 수 있어 시간복잡도가 O(1)이 됩니다.

코드

오답 코드(투 포인터)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, q;
long long temp, m;
vector<int> fuel;
int cnt;

int init(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  cin >> n >> q;
  fuel.resize(n);
  for(int i = 0; i < n; i++){
    cin >> fuel[i];
  }

  sort(fuel.begin(), fuel.end());
}

void question(int m){
  int idx = find(fuel.begin(), fuel.end(), m) - fuel.begin();

  if (idx >= n || fuel[idx] != m){
    cout << 0 << "\n";
    return;
  }

  cout << idx * (n - idx - 1) << "\n";
}

int main(){
  init();
  for(int i = 0; i < q; i++){
    cin >> m;
    question(m);
  }

  return 0;
}

정답 코드

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n, q;
  cin >> n >> q;
  
  vector<int> data(n);
  for (int i = 0; i < n; ++i) {
    cin >> data[i];
  }
  
  sort(data.begin(), data.end());

  unordered_map<int, int> index;
  for (int i = 0; i < n; ++i) {
    index[data[i]] = i;
  }

  while (q--) {
    int m;
    cin >> m;

    if (index.find(m) == index.end()) {
      cout << 0 << "\n";
    } else {
      int median_idx = index[m];
      if (m == data[0] || m == data[n - 1]) {
        cout << 0 << "\n";
      } else {
        int left_cnt = median_idx;
        int right_cnt = n - median_idx - 1;
        cout << left_cnt * right_cnt << "\n";
      }
    }
  }

  return 0;
}

성능