[백준] 1946. 신입사원

1946. 신입사원

1946번: 신입 사원

 

• 내 풀이
  • 서류 점수 낮은것부터 위로 전부 비교하려고 해서 시간초과
  • 테케는 맞았지만 시간초과

#서류, 면접 두개가 모두 나보다 잘난 사람이 있으면 안됨
#선발가능한 최대 인원 수
import heapq

test=int(input())
for tc in range(test):
    n=int(input())
    employee=[]
    cnt=n
  
    for i in range(n):
        #서류 성적, 면접 순위
        a,b=map(int,input().split())
        heapq.heappush(employee, (-a,b))
  
    for i in range(n):
        a,b=heapq.heappop(employee)
        lst=[]
        for i in range(n-i-1):
            a2,b2=heapq.heappop(employee)
    
            if b2<b: #면접 점수도 처음게 더 낮으면  
                cnt-=1
                lst.append((a2,b2))
                break
            else:
                lst.append((a2,b2))
        lst.extend(employee)
        employee=lst[:]
        heapq.heapify(employee)
  
    print(cnt)

 

• 다른 사람 풀이
  • 서류 점수로 정렬한 후 면접 점수가 더 높은 값으로 치환하면서 아래값들 비교

#서류, 면접 두개가 모두 나보다 잘난 사람이 있으면 안됨
#선발가능한 최대 인원 수
import heapq

test=int(input())
for tc in range(test):
    n=int(input())
    employee=[]
    cnt=1 #1등은 무조건 채용
  
    for i in range(n):
        #서류 성적, 면접 순위
        a,b=map(int,input().split())
        heapq.heappush(employee, (a,b))
  
    
    lst=[]
    idx=1
    a,b=heapq.heappop(employee)
    for i in range(1,n):
        a2,b2=heapq.heappop(employee) #a2가 a보다 서류점수는 낮은데

        if b2<b: #면접 점수는 b2가 더 높으면 
            a=a2
            b=b2
            cnt+=1
            continue
  
    print(cnt)