인사고과(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

사원의 [근무 태도 점수]와[동료 평가 점수]가 쌍으로 주어지며, 아래 조건에 맞는 사원들의 총계를 내림차순 정렬 후, '완호'라는 사원이 몇 번째인지를 구하는 문제이다. 가장 핵심적인 부분은 조건에 맞는 사원을 어떻게 선별할 것인가이다.

조건 = 다른 임의의 사원보다 두 점수가 낮지 않아야 한다

 

 

조건에 맞는 사원 선별

처음 문제를 접했을 때, 두 점수에 대해 정렬 후 이웃한 사원들을 비교하면 되지 않을까 생각했지만 예외 케이스가 존재해서 다른 방법을 찾으려 했다. 

 

규칙성을 찾기 위해 [근무 태도 점수] 와 [동료 평가 점수]를 x,y로 변환하여 좌표에 찍어 놓고 어떤 사원이 조건에 해당하는지를 파악해보았고, 아래 사진과 같은 점들이 조건에 맞다는 것을 알 수 있었다.

조건에 맞는 사원들(빨간색 점)

 

이를 x,y 로 표현해보자면 다음과 같다.

1. y의 값이 제일 큰 경우
2. [자신보다 y값이 큰 사원들의 x의 최댓값]보다 x값이 크거나 같은 경우

 

 

 

위에 해당하는 사원들을 구하기 위해서 아래와 같은 과정을 거치며, 그림과 같이 동작하게 된다.

1. y를 기준으로 내림차순 >> x를 기준으로 오름차순 정렬한다
2. 가장 큰 y를 갖는 사원들의 합과 번호를 totals 에 넣고, 현재까지의 최대 x값(pivot_x)를 갱신한다
3. y 보다 작은 사원들에 대해, pivot_x 값보다 x값이 크거나 같다면 totals에 넣어주고, pivot_x를 갱신한다

 

조건에 맞는 사원을 선택하는 과정

 

 

시간 복잡도

초기에 점수를 기준으로 정렬했기 때문에 O(nlogn) 이 걸리며, 이후 정렬한 리스트를 for문으로 순회하기 때문에 O(n)이 걸린다. 가장 많은 시간이 걸리는 것이 정렬이기 때문에 전체 시간복잡도는 O(nlogn)이며 scores의 최대 길이가 1e5이기 때문에 시간 내에 동작한다

 

 

코드

def solution(scores):
    size = len(scores)
    # 사원의 구분을 위해 scores에 사원 번호를 붙여줌
    for i in range(size):
        scores[i].append(i)

    # [근무 태도 점수]=x , [동료 평가 점수]=y
    # y 를 기준으로 내림차순, x를 기준으로 오름차순 정렬
    scores = sorted(scores, key=lambda x: (-x[1], x[0]))
    pivot_y = scores[0][1] # 가장 큰 y 값
    totals = []
    start = 0
    pivot_x = 0 # 가장 큰 x 값

    # y 값이 가장 큰 사원들에 대해 totals에 점수합(x+y)을 넣어준다
    for i in range(size):
        x, y, emp = scores[i]

        if y != pivot_y:
            break
        totals.append([x + y, emp])
        start += 1
        pivot_x = x # pivot_x를 최대값으로 갱신해준다

    # pivot_y보다 작은 사원들을 순회한다
    for i in range(start, size):
        x, y, emp = scores[i]
        if x >= pivot_x: # 자신보다 y값이 큰 사람들의 x 보다 큰 사원이면, totals에 넣어주고 pivot_x를 갱신한다.
            totals.append([x + y, emp])
            pivot_x = max(pivot_x, x)

    # 조건에 만족하는 사람들의 점수 합을 내림차순 정렬한다
    totals.sort(key=lambda x: (-x[0]))

    answer = -1
    index = -1

    # 완호라면 해당 순서를 저장하고, 해당 합과 같으며 가장 앞에 존재하는 위치를 구해서 반환한다.
    for i in range(len(totals)):
        if totals[i][1] == 0:
            index = i
            break
    for j in range(index, -1, -1):
        if totals[j][0] == totals[index][0]:
            answer = j + 1

    return answer

 

 

 

회고

[x,y] 쌍으로 노드가 주어지는 경우, 임의의 노드에 대해 두 값이 모두 작지 않은 노드를 어떻게 구하는지 경험할 수 있었다
만약 다음에 비슷한 문제가 나올 경우 바로 좌표를 떠올리면 시간 단축이 가능해보인다