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

문제 

문제 풀이 아이디어

• 튜플의 두 원소가 다른 사람보다 모두 작은 경우 제외하기 
• 첫번째 원소 내림차순, 두번째 원소 오름차순으로 정렬 후, 앞에서부터 두번째 원소의 최댓값을 갱신하면서 max 값보다 두번째 원소가 작은 사람은 두 값 모두 작다는 것이므로 인센티브 못받음
  • 첫번째 원소 기준으로 내림차순-> 순서가 뒤에 있으면 첫번째 원소가 작거나 같음 
  • 두번째 원소 기준으로 오름차순
    -> 두번째 원소의 이전에 나온 값들 중 최댓값보다 두번째 원소가 작으면 두 원소 모두 작다는 것을 보장함!  
    -> 첫번째 원소가 같은 경우 두번째 원소가 더 커서 max값이 갱신되면 첫번째 원소가 같지만 두 원소 모두 작다고 판단함, 따라서 오름차순 해주기 
       .. (2, 2)--max=2-->(2, 1)--1<max(2) 이므로 두 원소 모두 작다!--> 반례발생 
• 인센티브를 받을 수 있고, 완호보다 점수가 큰 사람들의 수 카운팅 
• 완호보다 점수가 큰 사람들의 수 +1 = 완호의 등수

리뷰

• 처음에 이중 for문으로 구현해서 시간복잡도가 O(N^2)이었음 
• 결국 해결하지 못하고 풀이를 참고함
• 대소비교는 역시 한번 정렬된 상태에서 두번째 원소도 고려하기

def solution(scores):
    answer = 0
    n = len(scores)
    w_scores = scores[0]
    w_sum = sum(w_scores)
    scores = sorted(scores, key = lambda x: (-x[0], x[1])) #(내림차순, 오름차순) 정렬 
    
    max_coworker = 0 
    for score in scores:
        if w_scores[0]< score[0] and w_scores[1]<score[1]: #완호 인센티브 못받음 
            return -1 
        #완호 점수보다 큰 사람들의 수+1=완호의 등수
        #이전에 나온 사람들의 동료 평가 점수 최댓값보다 동료평가 점수가 작으면 근무태도, 동료평가 모두 작은 사람 존재: 인센티브 못받음
        if sum(score)> w_sum and score[1]>= max_coworker:
            answer += 1
            max_coworker = score[1]
	
    return  answer+1