[python] 백준 1946 신입사원 파이썬

처음에 이 문제를 접했을 때에는 적어도 하나가 다른지원자보다 떨어지지 않는 자만 선발한다는 말에 꽂혀서 여집합을 이용해서 문제풀이를 해주려고 했다.

t = int(input())
ans = []
for _ in range(t):
    n = int(input())
    employee = []
    for i in range(n):
        a,b = map(int,input().split())
        employee.append([a,b])
    
    employee.sort(key= lambda x:[x[0],x[1]],reverse=True)
    answer = n

    for i in range(n):
        j = i+1
        while(j<n):
         #서류점수가 더 높은 지원자중 면접점수도 더 등수가 높은 지원자가 있다면
            if employee[i][1] > employee[j][1]:
                answer-=1
                break
            else:
                j+=1
                continue
            
    ans.append(answer)

for a in ans:
    print(a)

이게 처음에 풀이한 내 코드이다. 하지만 시간초과가 발생한다.
왜냐하면 문제를 보면 n의 범위가 1 ≤ N ≤ 100,000 로 굉장히 크다는 것을 알 수 있다.

그래서 수정한 코드는

import sys
t = int(input())

for _ in range(t):
    n = int(input())
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    arr.sort()
    #정렬시 서류 1등지원자는 언제나 합격이므로 기준점으로 잡아줌
    max = arr[0][1]
    cnt = 1
    for i in range(1,n):
        #서류등수가 더 낮은 지원자가 면접 등수가 더 높다면
        if arr[i][1]<max:
            cnt+=1
            max = arr[i][1]
    print(cnt)

이렇게 된다

서류 등수를 기준으로 오름차순으로 정렬을 진행해 준 후 이전의 지원자보다 서류등수가 낮은 참가자가 면접 점수 등수가 높다면 그때 카운트를 해주는 방식이다.

코드를 작성하는 거는 쉬운데 방법을 생각해내는게 어려운 문제였다.