[프로그래머스][C++] 인사고과
인사고과
문제 링크
분석
원호가 인센티브를 받을 수 있는지 확인하고, 받을 수 있다면 인센티브 대상자 중 몇 번째 순위로 받는지 구해야합니다.
만약 받을 수 없다면 -1을 반환해야합니다.
각 사원마다 근무 태도 점수와 동료 평가 점수가 있습니다.
특정 사원보다 두 점수가 모두 낮다면 인센티브를 받을 수 없습니다.
인센티브를 받을 수 있는 사원들의 두 점수 합으로 석차를 냅니다.
점수의 합이 같다면 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다.
scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.
완호의 점수는 항상 scores[0]에 위치합니다.
근무 태도 점수와 동료 평가 점수의 합이 높은 사원은 낮은 사원보다 특정 분야의 점수가 무조건 높습니다.
완전탐색은 시간 초과가 발생합니다.
풀이
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> scores) {
// 완호의 초기 등수는 1등으로 시작합니다.
int answer = 1;
// 완호의 점수를 추출합니다.
int wanhoAttitude = scores[0][0]; // 근무 태도 점수
int wanhoReputation = scores[0][1]; // 동료 평가 점수
int wanhoSum = wanhoAttitude + wanhoReputation; // 완호의 총 점수
// 근무 태도 점수 기준으로 내림차순 정렬합니다.
// 만약 근무 태도 점수가 같다면, 동료 평가 점수를 기준으로 오름차순 정렬합니다.
sort(scores.begin(), scores.end(), [](const vector<int>& a, const vector<int>& b)
{
if (a[0] == b[0])
{
return a[1] < b[1];
}
return a[0] > b[0];
});
// 동료 평가 점수의 최댓값을 저장합니다.
int maxReputation = 0;
for (const auto& score : scores)
{
// 현재 사원이 기존 최고 동료 평가 점수보다 낮기 때문에 인센티브를 받을 수 없는 경우
// 앞에서 나온 직원에게 근무 태도 점수와 동료 평가 점수 모두 낮게 된다.
if (score[1] < maxReputation)
{
// 탈락 대상이 완호인 경우 -1을 반환합니다.
if (score[0] == wanhoAttitude && score[1] == wanhoReputation)
{
return -1;
}
}
else
{
// 동료 평가 점수 최고값을 갱신해줍니다.
maxReputation = max(maxReputation, score[1]);
// 현재 직원의 총합 점수가 완호보다 높은 경우 높은 순위에 있으므로, 완호의 석차 증가
if (score[0] + score[1] > wanhoSum)
{
++answer;
}
}
}
return answer;
}
근무 태도 점수를 기준으로 정렬하는 이유는 다음과 같습니다.
- 근무 태도 점수를 내림차순으로 정렬하면, 순회 중에 만나는 직원들은 모두 이전 사람보다 근무 태도가 낮거나 같음이 보장됩니다.
- 즉, 앞에 있는 직원들은 항상 근무 태도가 더 높거나 같기 때문에 동료 평가 점수만을 비교하면 됩니다.
- 동료들의 점수를 순회하면서 현재까지 살펴본 동료 평가 점수의 최댓값을 유지하는 경우, 현재 직원 중 동료 평가 점수가 최댓값보다 작을 경우 앞의 직원에서 동료 평가가 높고, 근무 태도도 높다는 것을 보장할 수 있습니다.
성능 요약
시간 복잡도는 $O(n \ log \ n)$입니다.
- 정렬 함수 $O(n \ log \ n)$
- 정렬된 배열을 순회하는 반복문 $O(n)$
- $O(n \ log \ n) + O(n)$
공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.
테스트 성능
테스트 1 〉 통과 (0.01ms, 4.17MB)
테스트 2 〉 통과 (0.01ms, 4.21MB)
테스트 3 〉 통과 (0.01ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.18MB)
테스트 5 〉 통과 (0.01ms, 4.21MB)
테스트 6 〉 통과 (0.01ms, 3.66MB)
테스트 7 〉 통과 (0.01ms, 3.67MB)
테스트 8 〉 통과 (0.01ms, 4.2MB)
테스트 9 〉 통과 (0.02ms, 3.65MB)
테스트 10 〉 통과 (0.02ms, 4.16MB)
테스트 11 〉 통과 (0.07ms, 4.2MB)
테스트 12 〉 통과 (0.06ms, 4.17MB)
테스트 13 〉 통과 (0.13ms, 3.67MB)
테스트 14 〉 통과 (0.12ms, 3.72MB)
테스트 15 〉 통과 (0.75ms, 4.11MB)
테스트 16 〉 통과 (0.70ms, 4.22MB)
테스트 17 〉 통과 (1.45ms, 4.93MB)
테스트 18 〉 통과 (1.30ms, 5.08MB)
테스트 19 〉 통과 (8.66ms, 12.6MB)
테스트 20 〉 통과 (7.55ms, 12.4MB)
테스트 21 〉 통과 (8.22ms, 21.2MB)
테스트 22 〉 통과 (17.52ms, 21.5MB)
테스트 23 〉 통과 (16.37ms, 21.8MB)
테스트 24 〉 통과 (19.60ms, 21.4MB)
테스트 25 〉 통과 (16.72ms, 21.4MB)
테스트 26 〉 통과 (0.01ms, 4.2MB)
테스트 27 〉 통과 (0.02ms, 4.2MB)
테스트 28 〉 통과 (0.01ms, 3.68MB)
댓글남기기