[백준/BOJ] - 1946번 python 풀이 - 그리디

 

---

해당 문제는 단순하게 보면 서류와 면접 순위가 동시에 나보다 뛰어난 사람이 있으면 떨어뜨리는 문제이다.

그렇다면, 입력된 정보들을 서류 순위 기준으로 정렬을 한다.

그러면, 첫번째에 위치한 값은 서류 1등이기 때문에 비교를 할 필요가 없다.

그렇다는 것은 두번째부터 비교를 해야한다는 의미이며, 2번째에 위치한다는 것 자체가 탈락할 위험군이라는

의미이다.

서류에서 나보다 뛰어난 인원(정렬했을 때 idx가 나보다 앞에 있는 친구들)이 존재하기에,

그 인원들과의 면접 순위를 비교해봤을때 나보다 뛰어난지 아닌지를 비교하면 된다.

 

하나하나 다 비교하면 시간 복잡도가 비약적으로 상승하기 때문에 시간 초과를 방지할 겸

비교하려는 대상의 면접 순위와 서류가 나보다 뛰어난 친구들 중 면접 1등과 비교를 한다.

 

기본적으로 서류에서 지고 들어가기 때문에, 앞서 나온 친구들의 최고 면접 점수 보다 낮다면 탈락이 확정!

 

(앞선 친구들의 최고 면접 점수 보다 낮으면, 그 최고 면접 점수를 가진 친구에게 서류와 면접 순위에 밀리기 때문에~~)

---

정답 코드

 

import sys
input = sys.stdin.readline
T = int(input())
cnt = 0
for _ in range(T):
    P = int(input()) 
    arr = [list(map(int,input().split())) for _ in range(P)]
    arr.sort()
    top = arr[0][1]
    for i in range(1,P):#1~4
        if arr[i][1] < top:
            top = arr[i][1]
        else:
            cnt+=1
    print(P-cnt)
    cnt = 0

 

---

시간 초과 코드

 

import sys
input = sys.stdin.readline
T = int(input())
cnt = 0
for _ in range(T):
    P = int(input()) 
    arr = [list(map(int,input().split())) for _ in range(P)]
    arr.sort()
    for i in range(1,P):#1~4
        for j in reversed(range(i)):#i는 1, j는 0
            if arr[i][1] > arr[j][1]: #기준 지원자가 낮으면
                cnt+=1
                break
    print(P-cnt)
    cnt = 0