[백준] 저지 (10774번)

문제

학교 대표팀은 1부터 번호가 매겨진 저지를 학생 선수들에게 배분하고자 한다. 저지의 사이즈는 S, M, L 중 하나이다 (물론 S=small, M=medium, L=Large다).

각각의 선수들은 구체적인 저지의 번호와 선호하는 사이즈를 요구했다. 선수들은 만약 자신이 원했던 번호가 아니거나, 선호하는 사이즈보다 작은 사이즈의 옷을 받으면 불만이 생길 것이다. 그들을 만족시키기 위해서는, 요구하는 번호가 맞고 사이즈는 같거나 그 이상이어야 한다. 두 명의 학생들이 같은 저지를 받을 수은 없다.

조건을 만족하는 최대 학생 수를 구하는 프로그램을 작성하여라.

입력

첫 번째 줄은 저지의 수인 J가 주어진다.

두 번째 줄은 선수들의 수인 A가 주어진다.

다음  J줄에는 등번호 j인 저지의 사이즈가 주어진다. (1 ≤ j ≤ J)

마지막 A줄에는 선수들이 요구하는 사이즈와 번호가 입력된다.

테스트케이스의 50%는 1 ≤ J ≤ 103 , 1 ≤ A ≤ 103 를 만족하고, 

나머지 50%는 1 ≤ J ≤ 106 , 1 ≤ A ≤ 106 를 만족한다.

출력

만족할 수 있는 최대의 선수의 수를 출력한다.

---

알고리즘 분류에 disjoint-set으로 되어있어서 풀었는데, 전혀 필요없던 문제라 의아했다.

코드에서도 보이듯이 find와 union을 구현하려다가 없어도 될것같아 if 조건문만을 활용해서 문제를 해결했다.

문제 조건만 그대로 따라가도 문제를 푸는데 큰 어려움이 없다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%A0%80%EC%A7%80%20(10774%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
using namespace std;
int J, A, res;
int p[1000001];
int parent[1000001];

int find(int u) {
	if (parent[u] == u) return u;
	return parent[u] = find(parent[u]);
}


int main()
{
	cin >> J >> A;
	char tmp;
	for (int i = 0; i <= J; i++) parent[i] = i;

	for (int i = 1; i <= J; i++) {
		cin >> tmp;
		if (tmp == 'S') p[i] = 1;
		else if (tmp == 'M') p[i] = 2;
		else p[i] = 3;
	}

	for (int idx, i = 1; i <= A; i++) {
		cin >> tmp >> idx;
		if (find(idx) != idx) continue;
		else {
			if (tmp == 'L' && p[idx] != 3) continue;
			else if (tmp == 'M' && p[idx] < 2) continue;
			parent[idx] = 0;
			res++;
		}
	}
	cout << res;
}