[1946] 신입 사원 - 정렬 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/1946

1946번: 신입 사원

---

[ 문제 접근 ]

 

우선 처음에는 못풀었는데 풀고 답지? ( 다른 해답) 들을 보니 정답에 가까웠었다.

 

우선

1. pair<int,int> 를 원소로 하는 vec를 선언해주고 입력을 받는다.

2. vec를 오름차순 정렬하게 되면 first 값을 기준으로 정렬된다.

3.

1 6

...

4 3

5 4

가 있다면, 1 6은 반드시 합격이니 cnt++

6이랑 3이랑 비교하면 3이 작으니 3으로 pivot_y 변경하고 cnt ++

3이랑 4 비교하면 4가 크니 (5 , 4 ) 는 탈락.

 

만약 pivot_y를 계속해서 (1,6) 의 6으로 했으면 (5,4) 도 통과하는 일이 발생한다.

 

---

[ 최종 코드 ]

 

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

using std::cout; using std::cin;
using std::vector;

int T, N;
int cnt;
vector<std::pair<int, int>> score;

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

	cin >> T;
	while (T--) {
		cin >> N;
		score.reserve(N);
		int num = N;
		while (num--) {
			int x, y;
			cin >> x >> y;
			score.push_back({ x,y });
		}
		std::sort(score.begin(), score.end());

		int pivot_y = score[0].second;

		int cnt = 1;
		for (int i = 1; i < N; i++) {
			if(pivot_y > score[i].second) {
				pivot_y = score[i].second;
				cnt++;
			}
		}

		cout << cnt << '\n';
		score.clear();
	}
	return 0;
}

 

 

 

---

[ Key Point ]

 

👉 정렬문제 임을 아는게 point!

 

---

[ 다른 사람 풀이 ]

 

ref :: https://jaimemin.tistory.com/742