[Programmers] Q152995 인사고과

[Programmers] Q152995 인사고과

Question

Language: Python

Difficulty: Level 3

우선, 해당 문제의 input 사이즈는 최대 10만으로 O(n²) 이상의 시간복잡도를 가지는 알고리즘으로는 풀이가 불가능하다.

input 사이즈가 크기 때문에 모든 경우를 비교해서는 제한 시간 내에 풀이가 불가능하다.

두 점수가 모두 낮은 경우가 한 번이라도 낮으면 인센티브를 못 받기 때문에 정렬을 통해 인센티브를 받을 수 있는 조건이 되는 지 판별한다.

근무 태도 점수를 기준으로 내림차순 정렬을 하고, 동등한 경우에 대해서는 동료 평가 점수를 오름차순으로 정렬해서, 처음 부터 탐색을 진행한다. 이때 현재 까지의 최대 동료 평가 점수를 유지하면서 탐색을 수행하여 이보다 작은 경우에는 인센티브를 받지 못하게 된다. 동료 평가 점수는 이미 내림 차순으로 정렬되어 있는 상태에서 동료 평가를 비교하는 것이기 때문에 기준을 한 차원 낮춰 시간 복잡도를 줄인다.

Solution

from bisect import bisect_left
def solution(scores):
    answer = 0
    wanho_score=scores[0]
    scores.sort(key=lambda x: (-x[0],x[1]))
    max_score=0
    rankings=[]
    
    for score in scores:
        #근무 태도 점수도 낮고, 동료 평가 점수도 낮은 경우
        if score[1] < max_score:
            #완호 인경우 바로 종료한다.
            if score == wanho_score:
                return -1
            continue
        #인센티브를 받을 수 있는 대상을 따로 모아놓는다.
        rankings.append((sum(score)))
        #현재 까지의 최대 동료 평가 점수
        max_score=max(max_score,score[1])

    #정렬을 수행해서 인센티브를 받는 대상에 대한 석차를 구한다.
    rankings.sort(reverse=True)
    answer=rankings.index(sum(wanho_score))+1
        
    return answer