[Python 문제 풀이] 프로그래머스 '인사고과'

Programmers Lv.3 '인사고과' 파이썬 코드 및 풀이

조건파악

• 두 수가 있고 둘 중 하나라도 어느 다른 것보다 높아야 원소를 남긴다.
• 순서는 두 수의 합을 기준으로 한다.

 

접근

 일단 하나씩 뽑아서 서로 다른 원소들과 비교하면 시간초과가 발생한다. 따라서 사전 정렬을 통해 문제를 단순화할 필요가 있다.
 
 편의상 각 원소의 0번째 원소를 s0, 1번째 원소를 s1라 하겠다. 두 수 중 하나만 가지고 일단 내림차순으로 정렬시킨다. s0를 기준으로 정렬했다면 뒤에 오는 원소의 s1은 작거나 같을 테니 앞에서 순서대로 처리하면 된다.
 
 s0을 기준으로 정렬했으니 s1을 가지고 비교한다. 이를 위해서 앞에서부터 발견된 s1의 최대값을 기록한다. 이 최대값보다 작은 수가 발견된다면 해당 원소는 버린다.
 
 s0가 같은 경우가 있기 때문에 s0가 같은 그룹 내에서 발견된 s1의 최대값은 기록을 지연시킨다. s1은 s0와 반대로 큰 수가 뒤에 오도록 정렬하면 된다.
 
 결과적으로 두 수 중 하나를 기준으로 먼저 오름차순 정렬하고 나머지 하나는 내림차순으로 정렬하여 한 번씩만 처리하면 O(N)에 풀 수 있다.
 

의사코드

1. 완호의 점수를 저장
2. scores를 각 원소의 0번째 원소에 대해 내림차순, 1번째 원소에 대해 오름차순 정렬
3. rank와 max1를 모두 1로 초기화
4. scores에 대해 반복
5. 두 수가 모두 완호의 점수보다 크면 rank에 -1을 저장 후 반복 종료
6. 그렇지 않고 1번째 원소가 max1보다 같거나 크며 완호보다 점수의 합이 클 경우 rank에 1을 더함
7. max1을 업데이트
8. 반복 종료 후 rank를 반환 

 

구현

def solution(scores):
    s = scores[0]
    rank,max1 = 1,1
    for x in sorted(scores, key = lambda x : (-x[0], x[1])) :
        if x[0] > s[0] and x[1] > s[1] : # my score is unranked
            rank = -1
            break
        elif x[1] >= max1 and sum(x) > sum(s) : # the score is valid and higherly ranked
            rank += 1
        max1 = max(max1,x[1])
    return rank