[프로그래머스]Lv3. 인사고과(Python)

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

프로그래머스

 

문제 접근

 

고민은 길게 했지만 결국 시간 내에 풀지 못해 아쉬움이 남아 오답하면서  답을 보기 전 스스로 풀어보려고 1-2시간 고민했지만 결국 답안을 참고하여 오답하였다.

 

어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 인센티브 지급x

두 점수의 합이 높은 순으로 석차 + 동석차 수만큼 다음 석차 점프 

 

1. 하나씩 다 뽑아서 서로 다른 원소들과 비교해서 인센티브를 받지 못하는 사람을 거르면 시간초과가 발생

2. 근무평가 기준(첫 원소)으로 내림차순으로 정렬 

3. 동료평가 기준을 사용해 오름차순으로 정렬 시작 

 

당연히 동료평가 기준으로만 보면 정렬된 상태가 아니다.

하지만 근무평가 기준으로 보면 내림차순 정렬을 진행했기 때문에 뒤의 학생의 첫 번째 점수는 항상 앞의 학생의 첫 번째 점수보다 같거나 작다. 동료평가 기준으로 오름차순 정렬을 진행했기 때문에 나중에 탐색하는 학생의 두 번째 점수가 먼저 탐색하는 학생의 두 번째 점수보다 작은 경우가 있다면 인센티브를 지급받지 못한다. 

 

<시간 복잡도>

O(N)

 

코드

def solution(scores):
    
    answer = 1  #
    wanho = scores[0]
    wanho_score = wanho[0] + wanho[1]
    
    # 인센티브를 받지 못하는 사람을 거르기 위해 정렬 이용 
    # 근무평가 기준으로 내림차순, 동료평가 기준으로 오름차순 
    scores.sort(key=lambda x:(-x[0],x[1]))
    
    # 이전까지 확인한 동료평가 점수 중 가장 높은 점수를 저장 
    check = 0 
    
    for score in scores:
        # 두 점수가 모두 다른 사람보다 낮으면 인센티브x
        if wanho[0] < score[0] and wanho[1] < score[1]:
            return -1 
        
        # 이전까지 확인한 동료평가 점수 중 가장 높은 점수보다 현재 사람의 점수가 높거나 같으면 
        if check <= score[1]:
            # 완호 등수 체크하기 위한 조건문
            if wanho_score < score[0] + score[1]:
                answer += 1 
            # 동료평가 점수 중 가장 높은 점수 갱신 
            check = score[1]
    
    return answer