[백준] 1946번 문제

www.acmicpc.net/problem/1946

1946번: 신입 사원

하... 이 문제 푸는데 3시간 걸렸당.. ㅎ(알고리즘 포기할까..)

정렬까지는 했는데 좀 더 핵심이 되는 간단한 코드를 생각하지 못해서 2시간을 허비했던 것 같다.

분명 로프 문제와 거의 똑같은 문제였는데, 왜 생각하지 못했을까. 정말 나는 빡대가리

문제를 푸는데 1시간이 걸리면 안된다는 소리가 있었지만, 이번에는 오기가 생겨서 될때까지 하다가 지쳐서 결국 답을 봐버렸다.

다만, 답을 봤을 때 정말 감탄이 나왔다. 나는 O(n^2)이 걸렸는데, 답에는 O(n)의 시간 복잡도로 해결을 한 것이다. 참...

 

먼저 문제를 보자마자 멍했다. 문제를 계속 봤다. 10분정도? 그제서야 이해가 됬다. 아 각 사원들의 서류, 면접 성적의 순위가 주어질 때 합격할 수 있는 사원이 몇 명인지 구하는 문제라는 것

그렇다면 이걸 어떻게 구해야 할까?

먼저 벡터를 이용하자는 생각을 했다. 그리고 클래스를 만들어서 int형 변수 2개를 선언해서 각각 서류, 면접의 등수로 사용을 하고 서류의 등수를 기준으로 먼저 정렬을 한 뒤에 지지고 볶자라는 생각이 들었다.

여기까지는 좋았으나 그 정렬한 값을 가만히 냅두지를 못하고 활용하자는 생각에 갇혀서 헤어나오지를 못했다. 그래서 결국에는 시간초과가 뜨고, 컴파일 에러에 각양각색의 오류가 떴다.

 

나의 풀이

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

class Employee {
public:
	int num1;
	int num2;
	bool operator <(const Employee& e1)
	{
		return (num1 < e1.num1);
	}
	Employee(int n1, int n2) : num1(n1), num2(n2) {}
};

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t, num1, num2, res = 0;
		vector<Employee> v;
		cin >> t;
		for (int j = 0; j < t; j++) {
			cin >> num1 >> num2;
			v.push_back(Employee(num1, num2));
		}
		sort(v.begin(), v.end());
		for (int j = 1; j < t; j++) {
			bool failed = false;
			for (int k = 0; k <= j; k++) {
				if (v[j].num2 > v[k].num2) {
					failed = true;
					break;
				}
				failed = false;
			}
			if (!failed) res++;
		}
		cout << ++res << "\n";
	}
}

이렇게 풀면 안된다. ㅜㅜ

 

다른 사람 풀이 + 나의 생각 아주 조금...

#include <iostream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int t, num1, num2, res = 0;
		// 각 사원의 등수를 저장하기 위한 벡터
		vector<pair<int, int>> v;
		cin >> t;
		for (int j = 0; j < t; j++) {
			cin >> num1 >> num2;
			v.push_back({ num1, num2 });
		}
		// 정렬
		sort(v.begin(), v.end());
		int min = INT_MAX;
		for (int j = 0; j < t; j++) {
			if (min > v[j].second) {
				min = v[j].second;
				res++;
			}
		}
		cout << res << "\n";
	}
}

이렇게 풀어야지 암... 그렇고 말고

훨씬 간결하고 코드의 가독성도 좋다.