[BOJ/백준] 1946 신입 사원

import sys
 
T = int(input())
 
for tc in range(T):
    N = int(input())
    result = 0
    arr = [list(map(int,sys.stdin.readline().split())) for _ in range(N)]
    arr.sort()
    min_value = arr[0][1]
    for ind in range(N):
        if ind == 0:
            result += 1
        else:
            if min_value > arr[ind][1]:
                min_value = arr[ind][1]
                result += 1
    print(result)

처음에 입력 받은 그 상태로 서류점수 자체로 sort를 해줬다. 그러면  1번 지원자를 제외한 나머지 지원자들은 이미 서류점수에서, 자기보다 잘 본 사람이 있는 것이다. 

그렇기 때문에 면접점수에서 앞의 사람보다. 순위가 높으면, 두 분야에서 자기보다 잘 본 사람이 있는 것이기 때문에, 최종 탈락하는 것이다.

그래서, 제일 첫번째 지원자의 면접점수를 최소값으로 해주고, 이 값보다 좋은 순위가 있으면 교체를 해주면서 최종합격자 수를 늘려주면 된다.

 

하지만 이렇게 할시 무조건 처음에 sort를 해야하기 때문에 5000ms 이상의 시간이 걸린다.

 

import sys
 
T = int(input())
 
for tc in range(T):
    N = int(input())
    result = 1
    arr = [0]*(N+1)
    for _ in range(N):
        x,y = map(int,sys.stdin.readline().split())
        arr[x] = y
    min_value = arr[1]
    for ind in range(2,N+1):
        if min_value > arr[ind]:
            min_value = arr[ind]
            result += 1
    print(result)

개선한 방안은 어차피 중복되는 수는 없고 1~N 까지의 순위는 무조건 있기 때문에, 길이가 (N+1)인 1차원 리스트를 만들어주고, index가 서류점수 value가 면접점수가 되도록 한다.

그리고 그 다음은 위와 똑같이 진행해주면 된다.

sort를 진행하지 않기 때문에 실행시간이 확연히 줄어드게 된다.