1946번 신입사원

문제 출처 : https://www.acmicpc.net/problem/1946

사고과정

나를 제외한 모든 지원자를 비교해서 나보다 두 점수 중에 나보다 큰 값이 존재하면 안된다. 이게 핵심! 결국 모두 비교해야하는 것인가? 그렇다면 시간 복잡도는 O(n^2)일텐데
아하 sort를 통해 첫번째 값에 대해 일련으로 나열한다면 저절로 첫번째 값은 비교할 필요가 없겠다. 하지만 결국 모든 지원자에 대해 비교해야 해서 시간 복잡도는 유지되네... 일단 한 번 짜보자라는 마인드로 짯더니 역시나 시간 초과.

어떻게 해야 할까... 결국 첫 번째 값은 비교할 필요가 없고 두번째 값을 비교했을 때 나보다 작은 게 있으면 False!... 아 그렇다면 이전에 반복문을 통해 앞에 존재하는 값들은 변하지 않는다. 그런데 중요한 것은 결국 이 값들 중에 나보다 작은게 있냐? 이기 때문에 최솟값을 따로 저장해두고 비교해서 이보다 작다면 True 처리 해주면 되겠다.

결과는 성공이지만 시간이 상당히 오래 걸린다. 어디서 오래걸리는 것일까?

import sys

T = int(sys.stdin.readline().rstrip("\n"))

for _ in range(T) :
    N = int(sys.stdin.readline().rstrip("\n"))
    result = 1
    score = [list(map(int,sys.stdin.readline().rstrip("\n").split())) for s in range(N)]
    score.sort()
    
    interview = score[0][1]
    
    for i in range(1,N) :
        int_score=score[i][1]
        if int_score <interview :
            result+=1
            interview = int_score
            
    print(result)

interview에 적용한 방식을 그대로 적용하면 굳이 sort를 이용할 필요가 없다.
아니네

import sys
from collections import deque
T = int(sys.stdin.readline().rstrip("\n"))

for _ in range(T) :
    N = int(sys.stdin.readline().rstrip("\n"))
    freepass = deque([])
    score = [list(map(int,sys.stdin.readline().rstrip("\n").split())) for s in range(N)]
    
    freepass.append(score.pop())
    for i in range(1,N) :
        interview = score.pop()
        
        for j in range(len(freepass)):
            if freepass[j][0]>interview[0] and freepass[j][1]>interview[1] :
                #freepass에서 제거
            elif freepass[j][0]<interview[0] and freepass[j][1]<interview[1] :
                break
            freepass.append(interview)
            
    print(len(freepass))

que를 이용하여 O(n)으로 해결할 수 있을것 같았는데 중간에서 막혔다. 포기하자.

---

1. 문제에서 동점인 부분이 없다고 제시해줬으니 sort에서 lambda를 이용해 첫 번째 요소에 대해서만 sort를 행한다. -> 약 25%정도 효율 상승

astterd님의 풀이 나랑 어느 부분에서 차이가 나는 거지...?

2. tuple! 불변값이라면 list보단 항상 tuple을 이용하자. 두번째보다 또 20% 상승