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

문제 설명

완호네 회사는 연말마다 1년 간의 인사고과에 따라 인센티브를 지급합니다. 각 사원마다 근무 태도 점수와 동료 평가 점수가 기록되어 있는데 만약 어떤 사원이 다른 임의의 사원보다 두 점수가 모두 낮은 경우가 한 번이라도 있다면 그 사원은 인센티브를 받지 못합니다. 그렇지 않은 사원들에 대해서는 두 점수의 합이 높은 순으로 석차를 내어 석차에 따라 인센티브가 차등 지급됩니다. 이때, 두 점수의 합이 동일한 사원들은 동석차이며, 동석차의 수만큼 다음 석차는 건너 뜁니다. 예를 들어 점수의 합이 가장 큰 사원이 2명이라면 1등이 2명이고 2등 없이 다음 석차는 3등부터입니다.

각 사원의 근무 태도 점수와 동료 평가 점수 목록 scores이 주어졌을 때, 완호의 석차를 return 하도록 solution 함수를 완성해주세요.

---

제한 사항

• 1 ≤ scores의 길이 ≤ 100,000
• scores의 각 행은 한 사원의 근무 태도 점수와 동료 평가 점수를 나타내며 [a, b] 형태입니다.
  • scores[0]은 완호의 점수입니다.
  • 0 ≤ a, b ≤ 100,000
• 완호가 인센티브를 받지 못하는 경우 -1을 return 합니다.

---

입출력 예

scores	result
[[2,2],[1,4],[3,2],[3,2],[2,1]]	4

---

입출력 예 설명

5 번째 사원은 3 번째 또는 4 번째 사원보다 근무 태도 점수와 동료 평가 점수가 모두 낮기 때문에 인센티브를 받을 수 없습니다. 2 번째 사원, 3 번째 사원, 4 번째 사원은 두 점수의 합이 5 점으로 최고점이므로 1 등입니다. 1 등이 세 명이므로 2 등과 3 등은 없고 1 번째 사원인 완호는 두 점수의 합이 4 점으로 4 등입니다.

---

from heapq import heappush, heappop, heapify

def solution(scores):
    # score에 대한 최대 힙: [-score1, -score2]
    s_heap = [[-s[0], -s[1]] for s in scores] 
    heapify(s_heap) 
    
    # 0) s1_s2_dict, sum_heap 구하기
    # s1_s2_dict = {사원의 s1, 해당 사원보다 큰 점수를 받는 사람들의 최대 s2값}
    # sum_heap = 모든 원소가 -화 된, sum에 대한 최대 힙. [-sum, -score1, -score2]
    s1_s2_dict = {} 
    sum_heap = [] 
    s1_last, s2_max= 0, 0
    idx = 0
    while s_heap:
        idx += 1
        s = heappop(s_heap)
        heappush(sum_heap,[sum(s),s[0], s[1]])
        
        if idx == 1: #첫 iter 예외처리
            s1_last = s[0]
            s2_max = s[1]
            s1_s2_dict[s[0]] = 1
            continue
        else:   
            if s1_last != s[0]: #s1 값이 달라질 때, s1_s2_dict[s1]에 s1의 최대값 저장
                s1_s2_dict[s[0]] = s2_max
            s2_max = -max(-s2_max, -s[1])
            s1_last = s[0]
    
    # 1) 완호가 인센티브를 못받는 경우, return 
    [wanho_1, wanho_2] = scores[0]
    if -(s1_s2_dict[-wanho_1]) > wanho_2:
        return -1

    # 2) 완호가 인센티브를 받는 경우, 등수 찾기
    rank = 0
    while sum_heap:
        idx += 1
        [s, s1, s2] = heappop(sum_heap)

        # 인센티브 못 받는 경우, pass
        if s1_s2_dict[s1] and s1_s2_dict[s1] < s2:
            continue
        
        # rank = 완호와 같은 sum 갖는 경우 바로 break 하므로 동석차 고려할 필요 없음
        rank = rank+1
        
        if -s == wanho_1+wanho_2:
            break
            
    return rank

해냈다.. 나의 힘으로... 하지만 1시간 반 걸림

다른 사람의 풀이를 보니까 힙을 사용한 사람은 아무도 없는 것 같았다 .......... 

ㅋㅋㅋㅋㅋㅋㅋ

나는 무려 최대 힙을 두개나 써서 풀었는데 말야..!!!!!!!!

 

진짜 오래 걸린 이유:

1) 최대 힙이라서, 숫자가 - 되어서 들어가니까 모든 것에 혼란이 오기 시작했다

특히나 max 값을 구할 때, 최대값을 구하려면 다시 - 해준 후 max 하거나

min을 해줌으로써 구해야 했는데 그게 너무나도 헷갈렸다 ;)...

 

2) 초기값 설정 ㅡㅡ!!!!

while 을 돌면서 어떠한 값을 계속 갱신해나가야 하는데 (s1_last, s2_max 얘네들..)

idx를 안쓰고 꾸역꾸역 초기값을 설정해주려고 했는데 힙에서 나오는 값이 마이너스라는 것이 정말 ...

s2_max 처음 값을 0으로 넣어버리면 이후에 비교할 때 - 값과 비교해서 0이 더 크니까 또 안되고 ?

그렇다고 1로 넣어버리면 분기를 못타고 ?  

그런게 있었는데 ... 풀고나니까 기억이 안나네요.....

그래서 결국 idx 사용했다는 ㅎㅎ ... 

오늘의 교훈: 어거지 부리지 말자. 시간은 금이다 ㅎ...

---

풀이들을 보니까 sort 해도 통과할 수 있을 정도의 효율을 필요로 했나보다 .....

코드를 설명할 줄 알아야 하는데 중간중간 주석을 쓰는 것도 오래 걸렸다.

내 생각 정리가 이렇게 힘들줄이야 ^^... 당연하지 나도 엄청나게 헷갈렸으니까 ....

 

그나저나 프로그래머스 나의 풀이에 올라가는 거 너무 부끄럽다. 제발 수정할 수 있게 해주시거나 마지막 풀이를 올릴 수 있게 해주시면 안될까요 ?

왜냐면 진짜 코드 정리 안하고 되는지 보려고 했는데 확 풀려버려서.. 

누가봐도 안 친절하고 더러운 코드가 올라간단 말입니다 ㅜ!!!!!!!