[알고리즘] 인사고과 프로그래머스 Lv.3 파이썬

코드: Algorithm_test/Python3/프로그래머스/3/152995. 인사고과/인사고과.py at main · ddalkyTokky/Algorithm_test · GitHub

1. 정렬하자

자신보다 두 수의 합이 더 큰 친구들의 수를 세서 +1 을 하면 자신의 순위이다.

 

가장 먼저 들었던 생각은 정렬하자. 였다. 중간에 사실 스택을 써야하나? 라는 생각에 코드가 조금 꼬이긴 했는데, 결과적으론 잘 동작한다. (개념적으론 크게 다르지 않은 아이디어 였어서 작동하는거다. 고쳐야하긴 한다.)

2. 앞 수 기준으로만 정렬

그런데, 인센티브의 후보가 아닐 수 있는건, 나뿐만이 아니다. 다른 사람도 후보에서 탈락 되는 경우의 수가 있다.

 

1, 나를 제외한 나머지들을 앞 수 기준으로 정렬해서 뒷수만 비교해 나간다.

2. 그리고 다른 사람을 후보에서 탈락시킨 녀석은, 즉 두 수 모두가 뒤에 오는 사람의 두 수보다 큰 친구는 스택에 넣어서 관리한다.

3. 스택의 모든 녀석들과 싸워서 이긴 (두 수 중 하나라도 스택의 것보다 낫다면) 녀석들만 rank에 관여하도록 한다. 

3. 앞 수는 내림차순, 뒷수는 오름차순 정렬

하지만 위 방법은 3개 정도의 테스트 케이스 실패를 보여줬다..

 

그래서 고민 끝에 뒷 수도 오름차순으로 정렬했다.

 

이렇게 하면, 뒷 수 (이하 b) 만 비교하면 된다!! 이제 앞 수 (이하 a)  는 무조건 뒤로 갈수록 작아지기만 할 것이기에, b 조차도 이전 것보다 작다면, 후보에서 탈락된다! 

4. 최종 코드

def solution(scores):
    if(len(scores) == 1):
        return 1
    
    rank = 1
    
    a = scores[0][0]
    b = scores[0][1]
    ab = a + b
    
    stack = [[-1, -1]]
    
    scores = scores[1 : ]
    scores.sort(key = lambda x : (-x[0], x[1]))
    
    for s in scores:
        na = s[0]
        nb = s[1]
        nab = na + nb
        if((na > a) and (nb > b)):
            return -1
        if(nab > ab):
            while(len(stack) != 0):
                current = stack[-1]
                if((nb < current[1]) and (na < current[0])):
                    break
                else:
                    stack.pop()
            if(len(stack) == 0):
                stack.append(s)
                rank += 1
    return rank

5. 시간 복잡도

행위	시간 복잡도
정렬	O(N logN)
순회	O(N)
최종	O(N logN)