백준 1946번 그리디 기법

문제 : 각 지원자들의 서류 점수와 인터뷰 점수가 있다. 어떠한 합격자도 다른 모든 지원자들보다 한 가지 성적은 우수해야한다.

예시

(3 2) (1 4) (4 1) (2 3) (5 5) anwer : 4 ; (1,4)(2,3)(3,2)(4,1) 선발

푸는 법 : 그리디 기법으로

1. 서류 점수와 인터뷰 점수 중 무엇을 기준으로 할 지 정한다. 각 기준에 맞춰서 각 후보들의 점수를 정렬한다.

2. 기준 등수 1위의 다른 점수(;서류 점수를 기준으로 하면 서류 점수 1등의 인터뷰 점수) 를 구한다

다른 모든 지원자들은 기준 점수로는 기준 점수 등수 1위를 이길 수 없으므로 기준 점수 등수 1위의 다른 점수를 뛰어넘어야지 합격한다. 그리고 기준 등수 1위는 무조건 합격이므로 pass 를 1 늘린다

3. 기준 등수 2위의 다른 점수가 기준 등수 1위의 다른 점수를 뛰어넘는다면 합격이다. pass 를 1 늘린다.

이제 기준 등수 2위 밑으로 정렬된 애들은 기준 점수로는 기준 점수 등수 2위를 이길 수 없으므로 기준 점수 등수 2위의 다른 점수를 뛰어넘어야지 합격한다. 기준 등수 2위가 합격했다면 기준 등수 1위의 다른 점수는 이미 기준 등수 2위가 뛰어넘어서 criteria 가 업데이트 되었으므로 기준 등수 1위는 더 이상 고려하지 않아도 된다.

4. 모든 지원자의 점수를 점검할 때까지 반복한다.

import sys

t=int(input())

for _ in range(t):
    n=int(input())
    candidate=sorted([list(map(int,sys.stdin.readline().strip().split())) for x in range(n)],key=lambda X:X[0])
    pass=1
    criteria=candidate[0][1]
    
    for i in range(1,n):
        if candidate[i][1]<criteria:
            criteria=candidate[i][1]
            pass+=1
    print(pass)

처음에는 서류 점수, 인터뷰 점수 둘 다를 기준점으로 하여 각 점수 1위의 다른 점수를 기준으로 양쪽 필터링 ,2위의 다른 점수를 기준으로 양쪽 필터링,3위… 이런 식으로 동시에 필터링하려고 하였는데 그렇게 할 경우 이중 for 문을 써야하거나 양쪽에서 중복 pass 되는 애들이 발생하여서 되려 복잡해졌고 계속 fail 이 떴다. 너무 복잡하게 생각하지 말고 되도록 이중 for 문은 지양하자는 교훈을 얻었다. ‼️