[PS | programmers] 인사고과

문제

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

프로그래머스

문제 생각

임의의 두 수 i, j가 있다.
만약 근무태도 점수[i] < 근무태도 점수 [j] 이고 동료평가 점수[i] < 동료평가 점수 [j]
인 경우가 한 번이라도 있다면 i 는 인센티브를 받지 못한다.
그게 아니라면 두 점수의 합이 높은 순으로 석차를 낸다.

N = 10만이라면 → NlogN 알고리즘이 적합하겠다!!

문제 풀이

def solution(scores):
    wanho = scores[0]
		# 완호가 인센티브를 아예 못 받으면 -1을 출력한다. -> O(N)
    for score in scores : 
        if wanho[0] < score[0] and wanho[1] < score[1]:
            return -1
		# 정렬한다.
    scores = sorted(scores, key=lambda x : [x[0], -x[1]])

		# 뒤에서부터 prefix_max 값을 갱신시킨다.
    prefix_max = [0 for _ in range(len(scores))]
    
    prefix_max[-1] = scores[-1][1]
    for i in range(len(scores)-2, -1, -1):
        prefix_max [i] = max(prefix_max [i+1], scores[i][1])
    
		# scores와 prefix_max를 비교하면서 인센티브를 못 받는 사람을 추린다.
		incentive = []
    for j in range(len(scores)):
        if scores[j][1] >= prefix_max[j] :
            incentive.append(scores[j])
    result = 1
    for k in incentive :
        if sum(wanho) < sum(k):
            result+=1
    return result

생각하면 좋은 것

• 문제에서 준 제한을 생각하자. 굳이 몰라도 되는 여러 정보들을 다 구현하면서 코드를 짤 필요가 없다.
  • 우리가 알고 싶은 것은 완호의 석차! → 완호보다 높은 석차인 것들에만 집중하면 된다.
• 이후 나올 수 있는 모든 상황들을 파악한다. 위의 내용에서 생각할 수 있는 상황들은
  • 완호 ✅
  • 인센티브를 못 받는 다른 동료들 (low)
  • 인센티브를 받는 동료들 중 완호보다 score가 높은 동료들 (high)
  • 인센티브를 받는 동료들 중 완호보다 score가 낮은 동료들 (low)

 그래도 실수할 수 있으니 복잡한 여러 조건을 가지는 테케 하나를 만들어보고 그걸로 테스트를 해보자 !!

• 경계값 주의
  • 동석차일 때 → 동석차를 가지는 사람들의 석차와, 그 바로 다음 사람의 석차 주의!
  • 2차원 sorting 시 key = lambda x : [x[0], -x[1]] 은 아래와 같은 힘(?)이 있다. [ a , b ] 이 뒤에 있는 원소들의 → 첫번째 index값들은 a보다 큰 값들일 수 있다. → 첫번째 index값들은 a와 같은 값들일 수 있다. → 그렇다면 2번째 index 값들은 b보다 작거나 같다.