프로그래머스 - 인사고과

완호의 인센티브를 받는 유무와 완호는 몇등일까를 생각하는 문제

 

이런 문제는 조건을 잘 읽어야 해요.

 

1. scores의 길이는 최대 10^5, 점수도 최대 10^5

2. 완호가 인센을 못 받으면 -1을 return

3. 회사원 중 한명이라도 나보다 두 점수가 높은 사람이 있다면 인센에서 제외

4. 공동 1등이 2명이면 2등이 없고 3등부터 존재

 

일반 글씨는 처음에 접근한 방법이고 + 이후는 추후에 정답을 위해 생각한 거에요

1. 완호를 제외한 나머지를 scores로 재 정의하고

2. scores를 sort하여 정렬하고

3. scores를 순회하면서

3-1. 완호(me)가 인센을 못받는 조건인지 검사하고

3-2. 이중 반복문을 통해 해당 score index의 +1부터 조건을 통과하나 검사하고

3-3. 통과했다면 석차 계산을 위해 점수를 key로 가지는 딕셔너리에 명수를 저장한다.

4. 순회 후 인센티브 점수와 명수를 가진 딕셔너리를 점수로 sort하고

5. 완호의 등수를 계산한다.

 

+

2와 3번 사이에서 3-2를 줄이기 위해서 전처리로 미리 dictionary 형태로 미리 첫번째 점수에 대한 case 중 두번째 점수가 가장 큰 경우를 저장했어요.

3-1을 위의 단계로 옮겼어요.

완호보다 점수가 낮은 경우를 제외했어요.

 

def solution(scores):
    answer = 0
    
    number_employee = len(scores)
    me = scores[0]
    scores = scores[1:]
    scores.sort()
    incentive_dict = {}
    
    for index in range(number_employee-1):
        if scores[index][0] > me[0] and scores[index][1] > me[1]:
            return -1
        search_index = index + 1
        stop_flag = False
        while search_index < number_employee-1 and scores[index][0] < scores[search_index][0] and scores[index][1] < scores[search_index][1]:
            search_index += 1
            if scores[index][0] > scores[search_index][0] and scores[index][1] > scores[search_index][1]:
                stop_flag = True
        else:
            if not stop_flag:
                if not incentive_dict.get(sum(scores[index])):
                    incentive_dict[sum(scores[index])] = 1
                else:
                    incentive_dict[sum(scores[index])] += 1
    
    for rank_info in sorted(d.items(), reverse=True):
        score, number = rank_info
        if sum(me) >= score:
            break
        else:
            answer += number
                
    return answer

 

일단 시간초과 4개가 났습니다. 그래서 생각해본 것이 두번째 while문에서 났을 것이라고 생각하고

전처리로 1번째 점수에 대해서 딕셔너리 형태로 정리하는 것이었어요..

 

def solution(scores):
    answer = 0
    
    max_score_dict = {}
    first_value_list = []
    
    for score in scores:
        if max_score_dict.get(score[0]):
            max_score_dict[score[0]] = max(max_score_dict[score[0]],score[1])
        else:
            first_value_list.append(score[0])
            max_score_dict[score[0]] = score[1]
    
    first_value_list.sort()
    another_employee = len(scores)
    me = scores[0]
    scores.sort()
    
    incentive_dict = {}
    
    for index in range(another_employee):
        if scores[index][0] > me[0] and scores[index][1] > me[1]:
            return -1
        
        stop_flag = False
        
        for first_value_index in range(first_value_list.index(scores[index][0])+1, len(first_value_list)):
            first_value = first_value_list[first_value_index]
            if max_score_dict[first_value] > scores[index][1]:
                stop_flag = True
                break
        else:
            if not stop_flag:
                if not incentive_dict.get(sum(scores[index])):
                    incentive_dict[sum(scores[index])] = 1
                else:
                    incentive_dict[sum(scores[index])] += 1
    
    for rank_info in sorted(incentive_dict.items(), reverse=True):
        score, number = rank_info
        if sum(me) >= score:
            break
        else:
            answer += number
            
    answer += 1
    
    return answer

하나는 통과했는데 3개는 못했어요...

 

왜 일까 생각해봤는데 me에 대해서 생각하는 조건을 굳이 두번째 for문에 넣어야할까? 싶어서

 

첫번째로 옮겻어요

from heapq import heappush

def solution(scores):
    answer = 0
    
    small_score_dict = {}
    first_value_list = []
    
    for score in scores:
        if small_score_dict.get(score[0]):
            small_score_dict[score[0]] = max(small_score_dict[score[0]],score[1])
        else:
            first_value_list.append(score[0])
            small_score_dict[score[0]] = score[1]
    
    first_value_list.sort(reverse=True)
    another_employee = len(scores)
    me = scores[0]
    
    for first_value_index in range(first_value_list.index(me[0])):
        first_value = first_value_list[first_value_index]
        if small_score_dict[first_value] > me[1]:
            return -1
    
    scores.sort()
    
    incentive_dict = {}
    
    for index in range(another_employee):        
        stop_flag = False
        
        for first_value_index in range(first_value_list.index(scores[index][0])):
            first_value = first_value_list[first_value_index]
            if small_score_dict[first_value] > scores[index][1]:
                stop_flag = True
                break
        else:
            if not stop_flag:
                if not incentive_dict.get(sum(scores[index])):
                    incentive_dict[sum(scores[index])] = 1
                else:
                    incentive_dict[sum(scores[index])] += 1
    
    for rank_info in sorted(incentive_dict.items(), reverse=True):
        score, number = rank_info
        if sum(me) >= score:
            break
        else:
            answer += number
            
    answer += 1
    
    return answer

그런데도 25번째 테케가 실패하는 거임...

 

그래서 최적화 방법을 다시 생각해봤는데

 

1. 인사고과에서 탈락할 사람들을 딕셔너리형태로 접근하는 것이 빠를 것이라고 생각햇는데 똑같거나 느려졌어요.

2. 전처리하면서 각각의 첫번째 점수에서 두번째 점수를 최대로 하는 처리에서 거꾸로 for문 검사를 하도록 접근했는데 효과가 없었어요.

3. sorted가 오래걸릴 것이라고 생각해서 따로 인뎅싱하는 list를 했는데 아니었음!

4. 이게 정답이에요. 뭐냐면 ..

나보다 총합 점수가 낮은 사람은 굳이 생각할 필요가 없다.

 

이거에요.

그래서 sum_me라는 변수를 만들고 sum(me)를 할당해줬습니다.

 

from heapq import heappush

def solution(scores):
    answer = 0
    
    small_score_dict = {}
    first_value_list = []
    
    me = scores[0]
    sum_me = sum(me)

    for score in scores:
        if small_score_dict.get(score[0]):
            small_score_dict[score[0]] = max(small_score_dict[score[0]],score[1])
        else:
            first_value_list.append(score[0])
            small_score_dict[score[0]] = score[1]
    
    first_value_list.sort(reverse=True)
    another_employee = len(scores)
    
    for first_value_index in range(first_value_list.index(me[0])):
        first_value = first_value_list[first_value_index]
        if small_score_dict[first_value] > me[1]:
            return -1
    
    scores.sort()
    
    incentive_dict = {}
    
    for index in range(another_employee):
        if sum(scores[index]) <= sum_me:
            continue
        
        stop_flag = False
        
        for first_value_index in range(first_value_list.index(scores[index][0])):
            first_value = first_value_list[first_value_index]
            if small_score_dict[first_value] > scores[index][1]:
                stop_flag = True
                break
        else:
            if not stop_flag:
                if not incentive_dict.get(sum(scores[index])):
                    incentive_dict[sum(scores[index])] = 1
                else:
                    incentive_dict[sum(scores[index])] += 1
    
    for rank_info in sorted(incentive_dict.items(), reverse=True):
        score, number = rank_info
        if sum(me) >= score:
            break
        else:
            answer += number
            
    answer += 1
    
    return answer