문제 설명
완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다.
각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 1 ≤ scores의 길이 ≤ 100,000
- scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.
- scores[0]은 완호의 점수입니다.
- 0 ≤ a, b ≤ 100,000
- 완호가 인센티브를 받지 못하는 경우 -1을 return 합니다.
입출력 예
| scores | result |
| [[2,2],[1,4],[3,2],[3,2],[2,1]] | 4 |
문제 해설
문제설명을 분해해서 적용하면 쉽게 사용할 수 있다.
조건항을 분리해보자.
- 다른 임의의 사원보다 두 점수가 모두 낮은 사원은 인센티브 연산을 제외한다.
- 두 점수의 합이 높은 순으로 석차에 따라 인센티브가 지급된다.
- 동석차는 가능한 최고의 석차로 취급하며, 원래 석차는 제외한다. 1,2,3 이 있다면, 1등과 2등이 같을 때, 1,1,3 이 되는식.
위 3개의 조건항을 분리해서 적용하면 해결할 수 있다.
2번을 먼저 사용해서, 석차에 따라 정렬을 하고, 정렬된 석차에 비교연산을 진행하면 된다.
이때, 비교연산은 현재 진행된 석차에 따라서 비교연산을 진행하면 된다.
첫 번째 시도
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct CustomCompare {
bool operator()(const vector<int>& a, const vector<int>& b) const {
return a[0] + a[1] < b[0] + b[1];
}
};
int solution(vector<vector<int>> scores) {
int answer = 0;
priority_queue<vector<int>, vector<vector<int>>, CustomCompare> sortQ;
for (auto& def : scores) sortQ.push(def);
vector<int> back(2, 100001);
while (!sortQ.empty())
{
vector<int> now = sortQ.top();
sortQ.pop();
if (back[0] + back[1] >= now[0] + now[1])
{
back = now;
answer++;
}
if (now == scores[0]) return answer;
if (back[0] > now[0] && back[1] > now[1])
return -1;
}
return answer;
}실패
가능한 간단한 연산으로 데이터를 정렬해보았다.
문제 해설에 분리한 2번항을 기준으로 정렬한뒤, 전 값과 현재 값만을 비교하여 석차를 연산하였는데, 전체항을 비교해야함으로 당연히 한개의 값만 비교하게 됨으로 실패하였다.
두 번째 시도
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct CustomCompare {
bool operator()(const vector<int>& a, const vector<int>& b) const {
return a[0] + a[1] <= b[0] + b[1];
}
};
int solution(vector<vector<int>> scores) {
int answer = 0;
priority_queue<vector<int>, vector<vector<int>>, CustomCompare> sortQ;
for (auto i = scores.begin()+1; i != scores.end(); i++)
sortQ.push((*i));
sortQ.push(scores[0]);
vector<int> back(2, 100001);
vector<vector<int>> insert;
while (!sortQ.empty())
{
vector<int> now = sortQ.top();
insert.push_back(now);
sortQ.pop();
if (back[0] + back[1] >= now[0] + now[1])
{
back = now;
answer++;
}
if (now == scores[0]) {
for(auto& def : insert)
if (def[0] > now[0] && def[1] > now[1]) return -1;
return answer;
}
}
return answer;
}실패
이번에는, 현재까지 진행된 석차를 INSERT라는 vector배열에 삽입하여 현재 석차를 발견하였을 때.
문제 해설에 분리한 3번항을 진행하게 작업하였다.
그러나, 연산에 대하여 현재 진행되는 정렬값 중 인센티브에서 제외되는 경우를 해결하지 못하여 실패하였다.
[[7, 1], [6, 6], [5, 4], [5, 4], [6, 6]] 이 경우의 석차는
3 이다.
세 번째 시도
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct CustomCompare {
bool operator()(const vector<int>& a, const vector<int>& b) const {
return a[0] + a[1] < b[0] + b[1];
}
};
int solution(vector<vector<int>> scores) {
int answer = 0;
priority_queue<vector<int>, vector<vector<int>>, CustomCompare> sortQ;
for (auto& def : scores) sortQ.push(def);
vector<int> back(2, 100001);
vector<vector<int>> insert;
while (!sortQ.empty())
{
vector<int> now = sortQ.top();
sortQ.pop();
if (back[0] + back[1] >= now[0] + now[1])
{
bool chack = true;
for (auto& def : insert)
if (def[0] > now[0] && def[1] > now[1]) { chack = false; break; }
if (chack) {
back = now;
insert.push_back(now);
answer++;
}
}
if (now == scores[0]) {
for(auto& def : insert)
if (def[0] > now[0] && def[1] > now[1]) return -1;
return answer;
}
}
return answer;
}실패
한개의 경우만 실패한다. 정렬값과 1번항 2번항 3번항을 전부 반영하였음 에도 실패하였다.
실패한 원인을 규명하기 위해 분석한 결과, 생각보다 엄청 간단한 이유라고 생각된다.
[[4, 3], [5, 2], [5, 1], [4, 5], [4, 4]] 이 연산을 집어넣으면 4가 나온다.
3이 나와야 정답이다.
추측해보자면, 우선순위 큐 의 정렬방식을 살펴보아야 하는데,
우선순위 큐 는 이진트리 정렬방식을 사용하여, 값당 O(LogN)의 시간복잡도를 보장한다.
그렇다면, 정렬되는 순서가 7 7 6 9 8 가 들어가서,
9 8 7 7 6 가 나타나야 정상이다, 그렇지만 값은 9 8 6 7 7로 나타나게 된다.
우선순위 큐 에서 이진트리가 어떤방식으로 정렬되는지 를 이해해야 하는데,
우선 값이 순차적으로 들어갔을 때를 생각해보자.
7을 넣는다.
첫값이 들어가면 7이 된다.
다음 7을 넣어보자.
값이 같기 때문에 false가 나타나, 새로 들어오는 7은 우측으로 이동할 것 이다.
6을 넣어보자. 첫값에서 7보다 작기 때문에 true가 나온다.
위와같이 배치된다.
9를 넣어보자.
위와같이 배치되는게 정상이다. 9는 7보다 크기 때문에 false가 두번 나타나 두번째 7 의 우측에 배치될 것 이다.
하지만 틀렸다! 순서상 7은 같은 값 이기 때문에, 이렇게 정렬이 되지 않고 다음과 같이 정렬된다. 놀랍게도!
그 이유는 7은 같은 값이기 때문에, 9 다음에 7 그리고 6 7 이런식으로 정렬된다.
이진트리는 트리 순서대로 값이 출력되기 때문에, 좌측우선으로 9 7 6 7 로 나타난다. 여기서부터 트리구조가 망가지기 시작한다.
다음값으로 8을 넣어보자. 여기서 이제 최종적으로 문제가 터진다.
위와같이 8이 들어가야 하는데, 이미 7을 만났다. 그렇다면, 이진트리의 정렬방법 인 힙 정렬을 사용해서 정리해보자. 이때, 정렬알고리즘은 최대값이 위로가도록 정해놓았기 때문에, 최상단 노드는 항상 가능한 커야한다.
트리구조가 무너졌기 때문에, 루트노드에서 다음과 같이 정리된다.
8을 뺀 뒤, 8 위치에 우측에 있는 7을 올리고, 비교연산자 에서 true가 나타나는 값을 최상단으로 올린다.
최종적으로 위와같은 기형적?인 트리구조가 나타난다.
일단, 구조상으로 8은 6보다 크고, 7은 6보단 크기 때문에 이를 순서대로 표기하면 9 8 6 7 7 이 된다.
추측이 틀렸을 수도 있지만, 일단 값이 이렇게 나타난다...
네 번째 시도
#include <iostream>
#include <string>
#include <vector>
#include <list>
using namespace std;
bool customSort(const vector<int>& a, const vector<int>& b) {
return a[0] + a[1] > b[0] + b[1];
}
int solution(vector<vector<int>> scores) {
int answer = 0;
list<vector<int>> sortL;
for (auto& def : scores) sortL.push_back(def);
sortL.sort(customSort);
vector<int> back(2, 100001);
vector<vector<int>> insert;
while (!sortL.empty())
{
vector<int> now = sortL.front();
sortL.pop_front();
if (back[0] + back[1] >= now[0] + now[1])
{
bool chack = true;
for (auto& def : insert)
if (def[0] > now[0] && def[1] > now[1]) { chack = false; break; }
if (chack) {
back = now;
insert.push_back(now);
answer++;
}
}
if (now == scores[0]) {
for (auto& def : insert)
if (def[0] > now[0] && def[1] > now[1]) return -1;
return answer;
}
}
return answer;
}성공
그냥 비교 연산을 집어넣으면서 트리로 정렬하지 않고, list에 다 박아넣고 마지막에 sort를 돌렸다.
당연히 성공
'코딩테스트 문제 풀이 > 동적계획법(Dynamic Programming)' 카테고리의 다른 글
| 귤 고르기 (0) | 2024.05.22 |
|---|---|
| 마법의 엘리베이터 (0) | 2024.05.13 |
| [카카오 인턴] 경주로 건설 (1) | 2024.04.27 |
| (2023 KAKAO BLIND RECRUITMENT) 택배 배달과 수거하기 (0) | 2024.04.25 |
| 뒤에 있는 큰 수 찾기 (0) | 2024.04.24 |