[프로그래머스] 인사고과 (c++)

https://school.programmers.co.kr/learn/courses/30/lessons/152995

 

문제 요약) {근무 태도 : X, 동료 평가 : Y} 쌍이 배열로 주어진다.

• 0번 index 의 X0, Y0 값이 k 번째 index 의(0 < k < n) Xk, Yk 보다 작은 경우 인센티브를 못받는다.
• X0 + Y0 이 Xk + Yk 보다 작은 경우 순위에서 밀린다.

 

[풀이]

• 각 입력은 100,000 보다 작거나 같으므로, O(N) 혹은 O(NlogN) 알고리즘을 생각해야 함.
• 등수 = 전체 사원수 - 인센티브를 받지 못하는 사원수 - 0번째 사원보다 점수가 크거나 같은 사원수가 된다.
• i 번째의 X 와 Y 둘 모두 j 번째의 X 와 Y 보다 작은 경우 순위에서 제외되기 때문에 기준을 X로 잡고,
  동일한 X 의 값에 포함되는 최대의 Y 로 최적화 시킨다. MXY[Xi] = max(MXY[Xi], Y)
• 0~99,999 범위에 대해서 내림차순으로 스위핑하며 MXY[X] 보다 MXY[X + 1] 의 값이 더 크다면 최적화 해준다.
  • {{9, 8}, {8, 9}, {7, 8}, {6, 10} ...}  이 있는 경우 MXY[9] = 8, MXY[8] = 9, MXY[7] = 9, MXY[6] = 10 ... 로 정리된다
  • 스위핑이 끝나면, MXY[Xi] 값이 MXY[Xi + 1] 보다 작은 경우, Xi, Yi 보다 큰 사원이 있기 때문에 i 번째 사원은 인센티브를 못받는다.

 

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> scores) {
	int answer = scores.size(), sm = scores[0][0] + scores[0][1];
	vector<int> MXY(100001, 0);

	for (int i = 1; i < scores.size(); i++) {
		MXY[scores[i][0]] = max(MXY[scores[i][0]], scores[i][1]);
	}

	for (int i = 99999; i >= 0; i--) {
		MXY[i] = max(MXY[i + 1], MXY[i]);
	}

	if (MXY[scores[0][0] + 1] > scores[0][1]) {
		return -1;
	}

	for (int i = 1; i < scores.size(); i++) {
		if (MXY[scores[i][0] + 1] > scores[i][1]) {
			answer--;
		}
		else {
			if (sm >= scores[i][0] + scores[i][1]) {
				answer--;
			}
		}
	}

	return answer;
}