[프로그래머스-파이썬] 연습문제(LV3) : 인사고과

<문제출처>

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

프로그래머스

 

<체크포인트>

시간	쉽게해결	1시간이내	1시간 이상 or 몇 일 걸림	솔루션 보고 해결
체감 난이도	하	중	상	최상
이해도	완벽히이해	다소 헷갈리는 부분있음	이해못함
덧붙일 말

 

 

 

<고민 끄적끄적>

완전탐색을하면 시간초과에 걸릴 것 같아서 다른 방식을 생각해봤다.

정렬 후 스택을 활용하여 조건에 맞지않는 것은 빼 버리는방식으로 제거하였다.

여기서 조건이 있는데 첫 숫자에대해 오름차순, 그리고 두번 째 숫자에 대해 내림차순으로 정렬해야 한다.

두번째 숫자까지 내림차순으로 정렬해야 [[3, 2], [3, 4], [4, 4]] 와 같은 케이스를 통과할 수 있다(두번 째 내림차순 정렬을 안했을때를 생각해보면 쉽게 그 이유를 알 수 있다)

두번째 숫자 정렬을 조금 늦게 알아서 푸는데 시간이 좀 걸렸다..

 

 

최종코드

# 여기서 시간복잡도 O(n**2) 아래로 만들어야함
# scores = [[2, 2], [1, 4], [3, 2], [3, 2], [2, 1]]
# table  = [False, False, False, False, False] - > [True, True, True, True, False]
# 스택을 활용해보자
def make_posible_table(scores):
    table = [False]*len(scores)
    new = []
    for i, x in enumerate(scores):
        new.append((x[0], x[1], i))
    new.sort(key = lambda x : (x[0], -x[1]))  
    
    stack = []
    for x in new:
        if len(stack) == 0:
            stack.append(x)
            continue
        
        while (stack and stack[-1][0] < x[0] and stack[-1][1] < x[1]):
            stack.pop()         
        
        stack.append(x)
          
    for x1, x2, key in stack:
        table[key] = True  
    
    return table


# scores = [[2, 2], [1, 4], [3, 2], [3, 2], [2, 1]]
# table  = [True, True, True, True, False]
def get_ranking(table, scores):
    my_score, rank = sum(scores[0]), 1
    
    for i in range(1, len(scores)):
        if table[i] and my_score < sum(scores[i]):
            rank += 1       
    return rank
            
    
def solution(scores):
    posible_table = make_posible_table(scores)

    if not posible_table[0]:
        return -1    
    else:
        return get_ranking(posible_table, scores)