BOJ (C/C++) 10815번: 숫자 카드

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

10815번: 숫자 카드

 

---

풀이

숫자 카드와 상근이가 가지고 있는 카드를 각각 크기 순으로 정렬, 투포인터로 값을 비교했다.알고리즘엔 이진 탐색이라 되어 있어 이진 탐색으로도 풀어볼 예정

---

코드

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

vector <int> Card;
vector <pair<int, int>> Com;
int N, M;

bool cmp(pair<int, int> a, pair<int, int> b) { return a.second < b.second; }
bool ret(pair<int, int> a, pair<int, int> b) { return a.first < b.first; }
void Is_in(int size) {
	int n1, n2;
	n1 = n2 = 0;
	while (n1 < N && n2 < M) {
		if(n1>=N||n2>=M) break;
		if (Card[n1] == Com[n2].second) {
			Com[n2].second = 1;
			n2++;
		}
		else if (Card[n1] > Com[n2].second) {
			Com[n2].second = 0;
			n2++;
		}
		else n1++;
	}
	if (n2 != M) {
		for (int i = n2; i < M; i++) Com[i].second = 0;
	}
}

int main() {
	int c;
	scanf("%d", &N); // num of disk
	for (int i = 0; i < N; i++) {
		scanf("%d", &c);
		Card.push_back(c);
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d", &c);
		Com.push_back({ i,c });
	}
	sort(Card.begin(), Card.end());
	sort(Com.begin(), Com.end(), cmp);

	Is_in(M);
	sort(Com.begin(), Com.end(), ret);

	for (int i = 0; i < Com.size(); i++) printf("%d ", Com[i].second);

	return 0;
}