[프로그래머스/C++] 인사고과

문제

https://school.programmers.co.kr/learn/courses/30/lessons/152995?language=cpp#

프로그래머스

 

---

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int cmp(vector<int> a, vector<int> b)
{
    if(a[0]!=b[0])
        return a[0]>b[0];
    else
        return a[1]>b[1];
}

int solution(vector<vector<int>> scores) {
    int answer = 0;
    pair<int, int> p = make_pair(scores[0][0], scores[0][1]);
    vector<vector<int>> scores2(scores);
    vector<int> sum;
    sort(scores.begin(), scores.end());
    sort(scores2.begin(), scores2.end(), cmp);
    int p_score = p.first+p.second;
    for(int i=0;i<scores.size();i++)
    {
        if(scores[i][0]+scores[i][1]<p_score)
            continue;
        for(int j=0;j<scores.size();j++){
            if(scores[i][0]>=scores2[j][0]){
                sum.push_back(scores[i][0]+scores[i][1]);
                break;
            }
            else if(scores[i][1]<scores2[j][1]){
                if(scores[i][0]==p.first&&scores[i][1]==p.second)
                    return -1;
                break;
            }
        }
    }
    sort(sum.begin(), sum.end(), greater<int>());
    
    for(int i=0;i<sum.size();i++)
    {
        if(sum[i]==p_score)
            return i+1;
    }
    //return answer;
}

 

---

 

풀이

맨 처음 생각은 근무태도 점수를 오름차순정렬한 벡터와 동료평가 점수를 내림차순정렬한 벡터끼리 같은 인덱스에서의 점수를 비교하는 것으로 생각했다.

 

대략 요런 느낌으로다가 모든 선에 걸치지 않은 선을 찾으면 된다고 생각하였다.

 

그래서 처음 시도했던 방식

1. 벡터 하나를 근무태도 오름차순으로 정렬

    단, 점수가 같을 경우 동료평가 내림차순으로 정렬

2. 다른 벡터 하나는 동료평가 내림차순으로 정렬

    단, 점수가 같을 경우 근무태도 오름차순으로 정렬

3. for문으로 순회하면서 같은 인덱스의 숫자끼리 서로 비교하여 인센티브 받을 수 있는 사람은 sum 벡터에 합계 삽입

4. sum 오름차순으로 정렬

5. sum을 순회하여 완호와 합계가 같은 지점의 인덱스+1 값 반환

 

나름 같은 점수에 걸릴 때에 대해서도 고려하여 위와 같이 해보았는데 틀려버리기...

심지어 사이트에 올라온 테스트케이스는 다 정답처리 됐어서 더더욱 골머리를 앓았었다..

 

그리고 그 원인을 대략 찾았다.

근무태도 점수가 낮지만 동료평가 점수는 높은 사람, 근무태도 점수가 높지만 동료평가 점수가 낮은 사람들이 주를 이룰 때에만 내가 시도했던 방식이 얼추 맞아떨어지는 것이었다..

 

[[1,4],[2,6],[2,3],[2,1],[4,4],[4,2],[5,7]]을 받았을 때 [5,7] 빼고는 전부 인센티브를 받을 수 없다.

그러나 내가 시도했던 방식으로 한다면...

 

[1, 4]  [5, 7]   -> X
[2, 6]  [2, 6]   -> O
[2, 3]  [1, 4]   -> O
[2, 1]  [4, 4]   -> X
[4, 4]  [2, 3]   -> O
[4, 2]  [4, 2]   -> O
[5, 7]  [2, 1]   -> O

 

보이는 바와 같이 개판이 되어버렸다.

 

 

 

그래서 다시 생각해본 두번째 시도

 

1. 위와 동일

2. 근무평가 내림차순으로 정렬

그 이후도 일치

 

이 역시도 문제가 발생하였다.

 

[2,3] [4,3] -> O

[2,6] [4,0] -> O

[4,0] [2,6] -> O

[4,3] [2,3] -> O

 

역시 개판이 되었다.

 

 

 

그래서 결국 택한 것은 이중포문을 돌리는 것...

사실 이중포문은 엥간해서는 손대지 않으려고 했다. 왜냐 score로 100000개가 들어올 수 있었기 때문이다.

입력값이 저정도면 이중포문을 돌렸을 때 시간초과가 날 확률이 높았기에 시도하지 않으려 하였으나,,, 내 머리의 한계로 이중포문밖에 생각할만한 건덕지가 없었다.

 

그래도 나름 포문 돌아가는 수를 줄이려고 두번째 시도처럼 벡터 하나는 오름차순, 나머지 하나는 내림차순으로 정렬한 뒤, for문을 순회하여 근무태도점수가 일치하는 순간까지 동료평가 점수가 낮았던 적이 없으면 sum에 추가, 그렇지 않으면 넘기는 방식을 사용해보았다.

 

다행히 이때는 25번 테스트케이스 빼고 다 맞았다. 25번의 경우 시간초과로 실패...

순회 방식을 더 줄여야만 했다. 다행히 천사님들께서 힌트로 완호보다 총합이 낮은 애들은 배제하라 하시었다.

그 말씀에 힘입어 포문 안에 그 부분을 추가하였더니 드디어 통과!

 

근데 지금 다시보니 뭣하러 벡터 두개나 만들었나... 그냥 이중포문 돌릴거면 그렇게 안해도 됐는데 왜그랬나 싶어서 서러운 1인

---

 

다른 사람 풀이

다시 자괴감에 빠질 시간!! 어서 보고 배워라 나 자신

#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

bool comp(vector<int> a, vector<int> b)
{
    return a[0]!=b[0] ? a[0]>b[0] : a[1]<b[1];
}

int solution(vector<vector<int>> scores)
{
    int answer=0;

    int max_score=0;
    vector<int> target=scores[0], rank;
    sort(scores.begin(), scores.end(), comp);
    for(vector<int> score : scores)
    {
        if(score[1]<max_score)
        {
            if(score==target) return -1;
        }
        else
        {
            rank.push_back(score[0]+score[1]);
            max_score=max(max_score, score[1]);
        }
    }

    sort(rank.begin(), rank.end(), greater<int>());
    answer=find(rank.begin(), rank.end(), target[0]+target[1])-rank.begin()+1;

    return answer;
}

 

근무태도점수가 같지 않을 경우 내림차순, 근무태도점수가 같다면 동료평가 점수를 오름차순으로 정렬한다.

그 뒤 for문을 돌면서 동료평가 점수를 비교하는데 만약 동료평가 점수 중 가장 큰 점수를 넘기지 못한다면 근무태도점수부터도 이미 낮은 상태이므로 인센티브에서 제외, 점수를 넘겼다면 인센티브 받는 사람이므로 총합계를 rank에 삽입.

그 다음 rank를 내림차순 정렬하는 방식

 

사실 이게 내가 쓰고 싶었던 방식이었는데... 사실 비슷한 문제 푼 적 있었는데 방법 기억 안나서 어거지로 풀었는데....

사실 진짜 이렇게 하고 싶었는데... 오늘도 나의 한계를 보며 울고 갑니다...

---

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool comp(vector<int>a,vector<int> b){
    return (a[0]+a[1]) > (b[0]+b[1]);
}
int solution(vector<vector<int>> scores) {
    int answer = -1;
    int tx = scores[0][0];
    int ty = scores[0][1];
    sort(scores.begin(),scores.end(),comp);
    int rank = 1;
    int same = 0;
    vector<vector<int>> v;
    int sum = scores[0][1] + scores[0][0];
    for(int i = 0;i<scores.size();i++){
        vector <int> s = scores[i];
        //cout << s[0] << " " << s[1] << "\n";
        bool flag = true;
        for(int j=0;j<v.size();j++){
            if(s[0] < v[j][0] && s[1] < v[j][1]){
                flag = false;
                break;
            }
        }
        if(!flag) continue;
        if(s[0]+s[1] == sum){
            same++;
        }else if(s[0] + s[1] < sum){
            sum = s[0] + s[1];
            rank += same;
            same = 1;
        }
        if(s[0] == tx && s[1] == ty){
            answer = rank;
            break;
        }
        vector <int> t;
        t.push_back(s[0]);
        t.push_back(s[1]);
        v.push_back(t);
    }
    return answer;
}

 

이분의 경우 먼저 합계 내림차순으로 scores를 정렬하였다. 왜냐 합계가 큰 쌍이 작은 쌍보다 적어도 근무태도 점수나 동료평가 점수 중 하나라도 더 클 것이기 때문!

그렇게 내림차순으로 정렬한 scores를 for문으로 순회하면서 인센티브를 받을 수 있는 사람들인 v에 있는 사람들의 점수와 인센티브를 결정할 사람의 점수를 비교해준다.

인센티브 확정이면 v에 넣어주고 rank도 갱신해준다. 점수가 최근 등수 사람과 같으면 same만 증가시키고 더 적은 점수가 나타나면 아랫등수니까 rank에 여태 모은 same값을 더해준다.

만약 완호 점수가 나타나면 rank를 return.

 

점수 높은 사람이 낮은 사람보다 더 큰 점수 하나는 가지고 있을 것이라는 발상에서 나온 구현이다. 순회를 최대한 간소화한 코드다. 보고 배워야지...

---

#include <string>
#include <vector>

#include <algorithm>

using namespace std;

int solution(vector<vector<int>> scores) {
    int answer = 0;

    vector<int> wan_score = scores[0];

    //태도점수 기준 정렬
    sort(scores.begin(), scores.end(), [](const vector<int>& a, const vector<int>&b){return (a[0] == b[0]) ? a[1] < b[1] : a[0] > b[0];});

    int min = scores[0][1];

    for (const vector<int>& vTemp : scores)
    {
        if (vTemp[1] >= min)
        {
            if (vTemp[0] + vTemp[1] > wan_score[0] + wan_score[1])
            {
                ++answer;
            }
            min = vTemp[1];
        }
        if (vTemp[0] > wan_score[0] && vTemp[1] > wan_score[1])
        {
            return -1;
        }
    }

    return ++answer;
}

 

맨 위에 있던 구현과 별반 다르지는 않지만 rank 구하는 방식에서 차이가 있기에 가져와보았다.

위에서 점수를 다 모은 뒤 rank 벡터를 내림차순으로 정렬한 것과 달리 여기서는 인센티브 받는 사람 중 완호보다 점수가 높으면 answer를 증가시키는 방향으로 답을 구하고 있다.

 

 

---

 

후기

생각 좀 하고 살자. 요새 생각을 너무 안하고 바로 치려는 경향이 심해진 것 같다. 더 고민을 했더라면 저 위의 코드들과 비슷하게 구현을 했을텐데 그러지 못한 나 자신 반성하는 중. 바로 치지 말고 더 알고리즘을 생각해볼것!