문제 이해 단계
입력으로 사원의 정보가 주어지는데
각각 (근무 태도 점수, 동료 평가 점수)로 이루어져 있다.
목표는 사원의 등수를 정하는 것이다.
이 중에서 다른 사원과 비교했을 때,
한 번이라도 다른 사원보다 두 점수가 둘 다 낮은 사원은 등수에서 제외한다.
그리고 등수는 점수가 높은 순으로 선정한다.
동점자가 존재하면 그 사원은 같은 등수이고,
그 뒤에 등수 하나가 없어진 등수가 다음 사원에게 간다.
해당 조건에서 가장 처음에 들어온 입력(인덱스 0)
사원의 등수를 구하는 문제
제외됐다면 -1을 출력
문제 접근 단계
문제의 제한 사항부터 살펴보자.
scores의 길이, 그러니까 사원의 최대 수와 점수의 최댓값은 100,000이다.
여기서 더하는 행위는 근무 태도 + 동료 평가 밖에 없기 때문에
Int 자료형을 넘어갈 일이 없다.
따라서 자료형은 걱정할 필요가 없다.
이제 문제의 포인트를 살펴보자.
해당 문제에서 핵심은 뭘까?
두 점수가 한 번이라도
다른 사원보다 모두 낮으면 제외한다는 것이다.
그래서 그냥 직관적으로 해주면 편하다고 생각했다.
보통 이렇게 두 가지를 동시에 비교해야 하는 경우에는 하나를 고정해두고 하면 편하다.
그래서 정렬을 통해 하나의 수는
무조건 대소(크고 작음)가 비교되도록 한다.
만약 근무 태도를 기준으로 오름차순 한다면,
자기보다 높은 인덱스에 있는 동료 평가만 보면 된다.
왜냐하면 근무 태도를 기준으로 오름차순 했기 때문에,
보지 않아도 본인보다 같거나 높은 것이 확정적이기 때문이다.
이런 식으로 탐색을 해가면 된다.
핵심은 한 가지를 기준으로 정렬을 한다는 것이다.
근무태도를 기준으로 오름차순 정렬해서 지금 비교하고 있는 값이
자신보다 오른쪽에 있는 값의 동료 평가보다 작다면,
이는 근무태도와 동료평가가 모두 낮다고 평가하여 삭제한다.
(물론 근무태도가 같은 경우는 제외)
모든 사원들을 기준으로 탐색을 하고
남은 사원들만을 가지고 등수를 세우면 된다.
이제 문제 구현 단계로 넘어가 보자.
문제 구현 단계
// 각 점수를 분류한 구조체
struct Score{
int work;
int friends;
};
// 근무 태도 기준 오름차순
bool workOrder(Score a, Score b){
return a.work < b.work;
}
int solution(vector<vector<int>> scores) {
vector<Score> list;
Score target;
for(int i = 0; i < scores.size(); i++){
// 타겟이라는 변수에 담음
if(i == 0) target = {scores[i][0],scores[i][1]};
Score tmp = {scores[i][0],scores[i][1]};
list.push_back(tmp);
}
// 근무 태도 기준으로 오름차순 정렬
sort(list.begin(),list.end(),workOrder);
for(int i = 0; i < list.size()-1; i++){
bool del = false; // 삭제됐는지 체크
for(int j = i+1; j < list.size(); j++){
// 근무 태도가 같다면 둘다 낮은게 아니니까 패스
if(list[i].work == list[j].work) continue;
// 동료 평가가 오른쪽 인덱스에 있는 것보다 낮은 경우
if(list[i].friends < list[j].friends){
list.erase(list.begin()+i); // 삭제
del = true;
break;
}
}
if(del) i--; // 삭제됐을 경우 인덱스를 정상적으로 하기 위해
}해당 코드는 인센티브를 받지 못하는
사원을 제외하는 과정이 담긴 코드이다.
먼저 점수쌍을 좀 더 편하게 보기 위해
Score이라는 구조체를 사용했다.
이후 사용자 정렬 기준으로 workOrder 함수를 만들었다.
근무 태도 기준으로 오름차순 정렬하였다.
이중반복문을 사용하여
근무 태도가 가장 낮은 사원부터 기준으로 하여 탐색을 시작한다.
전체적으로는 위에서 설명했듯이 근무태도가 같은 것 이외에는,
근무 태도를 따로 비교하지 않는다.
오직 동료 평가를 사용하여 판단하여
리스트에서 사원을 삭제한다.
여기서 중요한 점은 오름차순 정렬했기 때문에
i 이전에 있는 인덱스는 살펴보지 않아도 된다는 것이다.
// 총합 기준 내림차순 정렬 기준
bool sumOrder(Score a, Score b){
int s1 = a.work + a.friends;
int s2 = b.work + b.friends;
return s1 > s2;
}
// 등수를 매기기 위해 총합 기준으로 내림차순 정렬
sort(list.begin(),list.end(),sumOrder);
int rank = 1; // 등수
int tmp = 0; // 동일 등수 뒤에 한번에 등수 오를때
bool success = false; // 타깃이 list에 들어있는지 확인
int cnt = 0; // 현재 총합 점수
for(int i = 0; i < list.size(); i++){
int sum = list[i].work + list[i].friends;
// 타깃을 찾았을 때
if(target.work == list[i].work
&& target.friends == list[i].friends) {
if(cnt != sum) rank += tmp; // 앞에 총합 점수와 같지 않을 경우 밀린 만큼 더해짐
success = true; // 타깃 찾았다고 체크
break;
}
if(cnt == sum) tmp++; // 총합 점수가 같을 경우 rank는 안더함
else {
// 총합 점수가 다를 경우 tmp에 담아뒀던 걸 더함
rank += tmp+1;
tmp = 0;
}
cnt = sum; // 총합 점수 동기화
}
int answer = rank;
if(!success) answer = -1; // 실패하면 -1 반환마지막으로 인센티브를 받을 수 있는 사원들만
남은 리스트에서 등수를 매기는 코드이다.
여기서는 총합 점수를 기준으로 등수를 매기기 때문에
sumOrder이라는 정렬함수를 만들었다.
이는 합 점수를 기준으로 내림차순 정렬하였다.
점수를 매기는 데에는 4가지의 변수를 사용했는데,
tmp는 점수에 넣을 포인트를 쌓아두는 변수라고 할 수 있다.
이를 미리 만들어두는 이유는 동일 등수 때문이다.
동일 등수가 존재할 경우 rank가 더해지면 안 된다.
하지만 다음 등수로 넘어갈 때, 1등 1등 3등 이런 식으로
2등은 생략되기 때문에 어딘가 저장은 해둬야 한다.
그게 tmp라는 곳에 저장해 둔 것이다.
나머지는 달아놓은 주석으로 충분히 알 수 있으리라 생각한다.
설명은 여기까지이다.
아래에 전체 코드를 올려놓고 설명을 마치겠다.
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 각 점수를 분류한 구조체
struct Score{
int work;
int friends;
};
// 근무 태도 기준 오름차순
bool workOrder(Score a, Score b){
return a.work < b.work;
}
// 총합 기준 내림차순 정렬 기준
bool sumOrder(Score a, Score b){
int s1 = a.work + a.friends;
int s2 = b.work + b.friends;
return s1 > s2;
}
int solution(vector<vector<int>> scores) {
vector<Score> list;
Score target;
for(int i = 0; i < scores.size(); i++){
// 타겟이라는 변수에 담음
if(i == 0) target = {scores[i][0],scores[i][1]};
Score tmp = {scores[i][0],scores[i][1]};
list.push_back(tmp);
}
// 근무 태도 기준으로 오름차순 정렬
sort(list.begin(),list.end(),workOrder);
for(int i = 0; i < list.size()-1; i++){
bool del = false; // 삭제됐는지 체크
for(int j = i+1; j < list.size(); j++){
// 근무 태도가 같다면 둘다 낮은게 아니니까 패스
if(list[i].work == list[j].work) continue;
// 동료 평가가 오른쪽 인덱스에 있는 것보다 낮은 경우
if(list[i].friends < list[j].friends){
list.erase(list.begin()+i); // 삭제
del = true;
break;
}
}
if(del) i--; // 삭제됐을 경우 인덱스를 정상적으로 하기 위해
}
// 등수를 매기기 위해 총합 기준으로 내림차순 정렬
sort(list.begin(),list.end(),sumOrder);
int rank = 1; // 등수
int tmp = 0; // 동일 등수 뒤에 한번에 등수 오를때
bool success = false; // 타깃이 list에 들어있는지 확인
int cnt = 0; // 현재 총합 점수
for(int i = 0; i < list.size(); i++){
int sum = list[i].work + list[i].friends;
// 타깃을 찾았을 때
if(target.work == list[i].work
&& target.friends == list[i].friends) {
if(cnt != sum) rank += tmp; // 앞에 총합 점수와 같지 않을 경우 밀린 만큼 더해짐
success = true; // 타깃 찾았다고 체크
break;
}
if(cnt == sum) tmp++; // 총합 점수가 같을 경우 rank는 안더함
else {
// 총합 점수가 다를 경우 tmp에 담아뒀던 걸 더함
rank += tmp+1;
tmp = 0;
}
cnt = sum; // 총합 점수 동기화
}
int answer = rank;
if(!success) answer = -1; // 실패하면 -1 반환
return answer;
}시행착오
스터디 때 1시간 시간제한 두고 풀었을 때는 못 풀었다.
처음에는 오름차순으로 해놓고 하니까
계속 틀렸다고 뜨고 해서 삽질만 하다가 끝났다.
근데 다시 풀어보니까 당연히 내림차순 정렬하는 게 쉽고
코드 짜기도 쉬운데 왜 오름차순 정렬했는지 모르겠다.
문제를 너무 어렵게만 생각한 것 같다. 지레 겁을 먹었다.
이 문제는 그리디 문제의 일종인 것 같은데
백준으로 치면 한 실버 1 될 것 같다.
생활비..