[백준 C++] 1946 신입 사원 - 정렬

1946번: 신입 사원

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

vector<pair<int, int>> OrderedList;

void Test()
{
	int N;
	cin >> N;

	OrderedList.reserve(N);
	OrderedList.clear();
	pair<int, int> Ranks;
	for (int i = 0; i < N; ++i)
	{
		cin >> Ranks.first >> Ranks.second;
		OrderedList.emplace_back(Ranks);
	}

	sort(OrderedList.begin(), OrderedList.end());

	int Count = 0;
	int MinRank = OrderedList.front().second;
	for (int i = 1; i < N; ++i)
	{
		int CurrentRank = OrderedList[i].second;

		if (CurrentRank < MinRank)
		{
			MinRank = CurrentRank;
		}
		else
		{
			++Count;
		}
	}

	cout << N - Count << '\n';
}

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

	int T;
	cin >> T;
	for (int i = 0; i < T; ++i)
	{
		Test();
	}
}

---

 

pair에 각 랭크를 저장하고 first 값으로 오름차순 정렬한 후에

모든 사람을 탐색하면서 자신보다 first 순위가 높은 사람 중의 second 순위 최소값과 비교하도록 했습니다.

 

다른 사람의 풀이를 보니 굳이 pair를 사용하지 않고도

벡터의 인덱스를 first 값으로 사용하고 내부 값에 second를 넣어서 순차 탐색하는 방식으로

정렬 연산 없이 푸는 방법도 존재했습니다.