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

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

 

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

프로그래머스

---

 

해결전략

 

정렬

 

 

 

 

---

 

처음 시도한 코드

 

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

struct Score
{
    int attitude;
    int coworker;
    int total;
    Score(int a, int b, int c) {
        attitude = a;
        coworker = b;
        total = c;
    }

    bool operator>(const Score& c) const {
        return total > c.total;
    }
};

vector<Score> v;
int workerRank[100000]; // 석차

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

    for (int i = 0; i < scores.size(); i++) {
        v.push_back({ scores[i][0], scores[i][1], scores[i][0] + scores[i][1] });
    }
    
    for (int i = 0; i < v.size(); i++){
        for (int j = 0; j < v.size(); j++){
            if (v[i].attitude < v[j].attitude && v[i].coworker < v[j].coworker)
            {
                v[i].total = -1;

                if (v[0].total == -1) // 원호가 인센티브 못 받는 경우
                    return -1;
            }
        }
    }

    sort(v.begin(), v.end(), greater<Score>()); // total이 많은 순서로 정렬

    workerRank[0] = 1;
    int cnt = 1;
    for (int i = 0; i < v.size(); i++) 
    {
        // 석차 구하기
        if (i > 0 && v[i - 1].total == v[i].total) {
            workerRank[i] = workerRank[i - 1];
            cnt++;
        }
        else {
            workerRank[i] = workerRank[i - 1] + cnt;
            cnt = 1;
        }

        // 완호의 석차
        if (v[i].attitude == scores[0][0] && v[i].coworker == scores[0][1]) {
            answer = workerRank[i]; 
            return answer;
        }
    }

    return answer;
}

 

테스트 22, 25 시간초과

---

 

정답 코드

 

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

struct Score
{
    int attitude;
    int coworker;
    int total;
    Score(int a, int b, int c) {
        attitude = a;
        coworker = b;
        total = c;
    }

    bool operator>(const Score& c) const {
        return total > c.total;
    }
};

vector<Score> v;
bool Dropped[100001];

int solution(vector<vector<int>> scores) {
    
    for (int i = 0; i < scores.size(); i++) {
        v.push_back({ scores[i][0], scores[i][1], scores[i][0] + scores[i][1] });
    }
    

    sort(v.begin(), v.end(), greater<Score>()); // total이 많은 순서로 정렬

    int answer = 1;
    for (int i = 0; i < v.size(); i++) 
    {
        for (int j = 0; j < i; j++) {
            if (v[j].attitude > v[i].attitude && v[j].coworker > v[i].coworker)
            {
                Dropped[i] = true;
                break;
            }
        }
        
        if (Dropped[i] == false && v[i].total > scores[0][0] + scores[0][1])
            answer++;

        // 완호의 석차
        if (Dropped[i] == false && v[i].attitude == scores[0][0] && v[i].coworker == scores[0][1]) {
            return answer;
        }
    }
    
    return -1;
}

 

 

 

 

---