[BOJ] 7795번 : 먹을 것인가 먹힐 것인가

1. problem : 

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

 

2. solution 1:

#include <bits/stdc++.h>
using namespace std;
int t;
vector<pair<int,int>> vc;


void mergeSort(vector<pair<int,int>>& v1, vector<pair<int,int>>& v2) {
	vector<pair<int, int>> temp;
	int v1idx = 0, v2idx = 0; 
	for (int i = 0; i < (v1.size() + v2.size()); i++) {
		if (v1idx == v1.size()) temp.push_back(v2[v2idx++]);
		else if (v2idx == v2.size()) temp.push_back(v1[v1idx++]);
		else if (v1[v1idx].X <= v2[v2idx].X) temp.push_back(v1[v1idx++]);
		else temp.push_back(v2[v2idx++]);
	}
	for (int i = 0; i < v1.size() + v2.size(); i++) {
		vc.push_back(temp[i]);
	}
}
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	cin >> t; 

	for (int i = 0; i < t; i++) {
		int n, m; 
		vc.clear();
		vector<pair<int, int>> va;
		vector<pair<int, int>> vb;
		cin >> n >> m; 
		for (int i = 0; i < n; i++) {
			int x;
			cin >> x;
			va.push_back(make_pair(x,'A'));
		}
		for (int i = 0; i < m; i++) {
			int x; 
			cin >> x;
			vb.push_back(make_pair(x, 'B'));
		}
		//merge sort 실행 
		sort(va.begin(), va.end());
		sort(vb.begin(), vb.end());
		mergeSort(va, vb);
		int ans = 0;
		int cnt = 0;
		for (int i = 0; i < vc.size(); i++) {
			if (vc[i].Y == 'A') {
				ans += cnt;
			}
			else cnt++;
		}
		cout << ans << '\n';
	}
}

mergeSort 사용

 

3. solution 2 :

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/c8698bc57ac343dea8f836660aecc0b4
#include <bits/stdc++.h>
using namespace std;

int main(void){
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while(t--){
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> v(n+m);
    for(int i = 0; i < n; i++){
      int a;
      cin >> a;
      v[i] = {a, 0};
    }
    for(int i = n; i < n+m; i++){
      int b;
      cin >> b;
      v[i] = {b, 1};
    }
    sort(v.begin(), v.end());
    int cnt = 0; // 현재까지 나온 b의 개수
    int ans = 0;
    for(int i = 0; i < n+m; i++){
      if(v[i].second == 0) // 현재 보는 수가 A에 속한 수
        ans += cnt;
      else // 현재 보는 수가 B에 속한 수
        cnt++;
    }
    cout << ans << '\n';
  }
}

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0F/solutions/7795.cpp

basic-algo-lecture/0x0F/solutions/7795.cpp at master · encrypted-def/basic-algo-lecture

하나의 벡터로 훨씬 더 깔끔하게 처리하였다. 나도 써먹어야겠다.