프로그래머스 - 인사고과

값을 여러 쌍을 준 뒤, 특정한 인덱스가 몇 번째로 위치하는지에 대한 문제를 프로그래머스에서 몇 번 본듯한 기억이 있었다.

지금 정리해두면 나중에 유용하다 생각해 글을 쓰게 됐다.

완전 탐색

1. 태도, 동료 점수 모두 자신보다 큰 사원이 있을 경우 해당 사원을 제외한다.

2. 각 사원들의 점수 총합을 구한 뒤, 점수를 기준으로 내림차순 정렬을 해 원호가 몇 번째로 큰지 본다.

만약, 원호가 제외됐을 경우 -1을 반환한다.

 

시간복잡도 계산

1번의 경우 모든 사원을 봐야 하기 때문에 N^2의 시간 복잡도 발생

2번의 경우 정렬에 Nlog(N), 원호의 위치를 찾는 과정에서 N의 시간 복잡도 발생

총 시간 복잡도는 N^2 + Nlog(N) + N으로, N = 100,000이기에 시간 초과가 발생한다.

 

틀린 풀이

태도 점수가 가장 큰 사원과 동료 점수가 가장 큰 사원을 각각 한 명씩 뽑은 뒤

각각 O(N)의 탐색으로 이 사원들과 비교해 점수가 낮을 때마다 값을 카운팅 했다.

카운팅이 2가 되면, 태도와 동료 점수 모두 뒤처진다 판단해 제외했지만 다음과 같은 반례가 나왔다.

 

input
[[2, 4], [3, 3], [2, 5], [5, 2], [4, 4]]

answer

4

 

정답 풀이

다른 사람의 풀이를 참고한 결과 내가 너무 복잡하게 생각했다.

태도 점수를 내림차순, 동료 점수를 오름차순 정렬했다. 반대로 해도 상관없다.

 

O(N)로 탐색하는 과정에서 2가지 조건을 본다.

1. 특정 사원의 점수 모두가 원호의 점수보다 높다면 -1을 리턴한다.

2. 현재 사원의 동료 점수가 현재 탐색한 동료 점수의 최댓값 이상인 경우 이를 갱신한다.
이 과정에서 점수의 총합이 원호의 점수 총합보다 높다면 answer 값을 1 증가시킨다.

 

2번을 만족하지 못한 사원은 인센티브를 받지 못하니 제외한다.

 

정렬 기준을 저렇게 한 이유

이 풀이에서 가장 중요한 요소.

태도 점수를 기준으로 내림차순을 했으니 i 번째의 원소의 태도 점수는 i + 1의 원소보다 크거나 같다.

 

점수가 같다면 동료 점수는 낮은 사원이 더 앞으로 가게 되니
2번 조건에서 동료 점수의 최댓값을 만족해 인센티브 대상에서 제외되는 상황이 발생하지 않는다.

 

점수가 작지만, 동료 점수가 같거나 큰 경우, 두 점수 다 작지 않게 되니, 2번 조건문에 진입할 수 있다.

 

코드

def solution(scores):
    answer = 1
    oneho = scores[0]
    scores.sort(key=lambda x:(-x[0], x[1]))
    
    co = 0
    for a, b in scores:
        if oneho[0] < a and oneho[1] < b:
            return -1
        if co <= b:
            if oneho[0] + oneho[1] < a + b:
                answer += 1
            co = b
    return answer