[그리디/백준] 1946번: 신입 사원

-문제 풀이: https://www.acmicpc.net/problem/1946

 

-정답 풀이:

0열을 기준으로 오름차순 정렬하면 서류에서 우수한 사람들을 가릴 수 있다. 

기본적으로 서류에서 0등은 뽑히므로 count=1로 시작한다. 

서류에서 우수한 사람보다 면접에서 더 우수하면 그 사람은 면접에서라도 뛰어나므로 채용이 된다. 

채용된 사람의 면접 점수를 기준으로 다음을 이어나가면 된다

for _ in range(int(input())):
    n=int(input())
    data=[]
    for _ in range(n):
        data.append(list(map(int,input().split())))
    zero=sorted(data,key=lambda x: x[0])
    #선발인원 수 
    count=1
    result = zero[0][1]
    
    for i in range(1,n):
        if zero[i][1] < result:
            count+=1
            result=zero[i][1]       
    print(count)

 

-시간초과 풀이: 

이중 for문으로 풀었는데 이렇게 하면 시간복잡도가 n**2가 되어서 시간초과가 발생한다 

for _ in range(int(input())):
    n=int(input())
    data=[]
    for _ in range(n):
        data.append(list(map(int,input().split())))
    zero=sorted(data,key=lambda x: x[0])
    one = sorted(data, key=lambda x: x[1])
    count=0
    
    for i in range(n):
        for j in range(i+1):
            if zero[j][1] > zero[i][1]:
                count+=1
    print(n-count)