[프로그래머스] Level 3: 인사고과

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

프로그래머스

 

두 점수의 합이 10인 사원이 있다고 하자..

이 사원이 인센티브를 받지 못하는 경우는 최소 두 점수의 합이 12이어야 한다. (1씩 높은 경우)

따라서, 두 점수의 합이 10보다 아래인 사원들은 굳이 비교하지 않아도 된다.

 

또한, 사원 중에 { 4, 5 }, { 4, 4 }가 있다고 하면, { 4, 5 }만 비교에 사용해도 되기 때문에, { 4, 4 }는 사실상 필요 없다.

 

점수가 이전과 같은 경우, 순위는 그대로여야 한다.

점수가 이전과 다른 경우, 동 순위로 밀린 만큼 뒤의 순위로 지정해야 한다.

따라서 최종 순위와, 동 순위를 고려하지 않았을 때의 순위를 저장해둬야 한다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

// 근무 태도 점수 + 동료 평가 점수가 높은 순으로 내림차순 정렬 (점수 합이 같은 경우, false를 반환)
bool cmp(const vector<int>& a, const vector<int>& b)
{
	if ((a[0] + a[1]) == (b[0] + b[1])) return false;
	return (a[0] + a[1]) > (b[0] + b[1]);
}

int solution(vector<vector<int>> scores) {
	if (scores.size() == 1) return 1;

	pair<int, int> Wanho = { scores[0][0], scores[0][1] }; // 정렬 전, 원호 점수 저장
	sort(scores.begin(), scores.end(), cmp);

	queue<pair<int, int>> q; // 두 점수가 모두 낮은 경우를 확인하기 위한 큐
	// 현재 사원의 점수의 합보다 큰 사원의 점수만 저장된다.

	// 현재 순위, 이전 점수, 동 순위 스택
	int Index = 0, Prev = -1, Stack = 0;
	for (int i = 0; i < scores.size(); ++i)
	{
		int First = scores[i][0], Second = scores[i][1], Sum = First + Second;

		queue<pair<int, int>> qq; // 현재 사원을 검사 후, 남아있는 사원들
		bool Check = true; // 두 점수가 모두 낮은지 여부

		while (!q.empty())
		{
			// 두 점수가 모두 낮은 경우
			if (First < q.front().first && Second < q.front().second)
			{
				// 큐가 다 비워지지 않았는데 두 점수가 모두 낮을 수 있으므로, 새 큐로 옮긴다.
				while (!q.empty()) { qq.push(q.front()); q.pop(); }
				Check = false;
				break;
			}

			// 현재 사원 큐에 있는 애보다 크거나 같으면, 대체할 수 있으므로 기존 큐를 지운다.
			if (First >= q.front().first && Second >= q.front().second) q.pop();
			else { qq.push(q.front()); q.pop(); } // 변화가 없으므로, 새 큐로 옮긴다.
		}

		// 두 점수가 모두 낮지 않은 경우
		if (Check)
		{
			// 두 점수의 합이 이전의 두 점수의 합과 다르면, 무조건 순위 변동이 일어난다. (ex. 1등 -> 2등)
			if (Prev != Sum)
			{
				Prev = Sum; // 변동된 순위로 초기화한다. (1등만 검사하다 2등으로 바뀌었으면, 이제 2등을 기준으로 잡음)
				Index += Stack + 1; // 동 순위에 쌓인 스택을 모두 합쳐 순위를 정한다.
				Stack = 0; // 동 순위 스택을 초기화 한다.
			}
			else Stack++; // 동 순위 스택을 올린다.

			// 순위 계산이 끝나면, 원호인지 확인한다.
			if (First == Wanho.first && Second == Wanho.second) return Index; // 원호면, 그대로 현재 순위 반환
			qq.push({ First, Second }); // 원호가 아니면, 새 큐에 추가
		}
		// 두 점수가 모두 낮은 경우
		// 만약에 그게 원호라면, -1 반환
		else if (First == Wanho.first && Second == Wanho.second) return -1;

		// 최종 계산이 끝난 큐로 교체
		q = qq;
	}

	return 0;
}