[Programmers] 인사고과(Lv.3)

풀이 소요시간 : 실패(60분 초과)

확실히 프로그래머스 레벨3 수준은 쉽지 않은것같다. 한계점을 높이기 위해 조금더 머리아픈 문제들을 많이 풀어볼 예정이다.

실패 원인

시간초과

언뜻보기에 매우 쉬운 문제로 N의 크기가 100,000 이라 O(N^2) 시간 복잡도로 풀릴것 처럼 보였다. 하지만 레벨 3 문제가 아니랄까봐 시간초과로 실패했다.

이후 내 머리로는 O(NlogN) 의 풀이가 떠오르지 않아, priority_queue 를 사용한 O(NlogN) 의 풀이 하나를 발견했는데, 이상하게 하나의 테스트 케이스에서 시간초과가 발생했다. 그냥 재수가 없는거같다.

결국 정렬을 위주로 풀이한 코드 하나를 찾아서 학습하며 구현할 수 있었다. 주어진 코드를 해석하고 내것으로 받아들이는데도 꽤 많은 시간을 소비했다. 더욱 성장할 수 있도록 양분삼아야겠다.

전체 코드

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

int N;
map<int, int> Map;
vector<int> ScoreList;

struct Emp {
    int S1;
    int S2;
};

bool Cmp(Emp A, Emp B) {
    return A.S1 > B.S1;
}


int solution(vector<vector<int>> scores) {
    
    int s1 = scores[0][0];
    int s2 = scores[0][1];
    vector<Emp> Vector;
    
    
    for(vector<int> E : scores) 
    {
        if(E[0] > s1 && E[1] > s2)
        {
            return -1;
        }
        Vector.push_back({E[0], E[1]});
    }
    //Vector 에 직원 점수정보 투입
    
    
    
    sort(Vector.begin(), Vector.end(), Cmp);
    // 제 1 점수 기준으로 내림차순 정렬
    
    
    
    for(int i = 0; i < Vector.size(); i++)
    {
        int Flag = false;
        int Sum = Vector[i].S1 + Vector[i].S2;
        
        // i번째 S1 값이 j번째 S1 값보다 항상 작거나 같다. 내림차순
        for(int j = 0; j < i; j++)
        {
            if(Vector[i].S1 < Vector[j].S1 && Vector[i].S2 < Vector[j].S2)
            {
                Flag = true;
                break;
            }
        }
        
        
        if(Flag == false)
        {
            if(Map[Sum] == 0)
            {
                ScoreList.push_back(Sum);
            }
            Map[Sum]++;
        }
        
    }
    
    
    sort(ScoreList.rbegin(), ScoreList.rend());
    //인센티브 받는 직원의 합 -> 내림차순 정렬
    
    int Rank = 1;
    for(int i = 0; i < ScoreList.size(); i++)
    {
        if(ScoreList[i] == s1 + s2) return Rank;
        else
        {
            Rank += Map[ScoreList[i]];
        }
    }
    
    return -2;
    
}