[TIL/크래프톤 정글9기] 29일차(백준 신입 사원 / 그리디)

이번 백준 문제는 그리디 문제이다. 해당 문제를 풀면서 예제만 이해하는데 오랜시간이 걸렸다. 왜냐하면 나는 서류, 면접의 점수를 주는 줄 알았는데 도저히 예제가 저렇게 나오는지 몰라서 지피티한테 물어보니 점수가 아닌 등수 였다....
앞으로 문제를 읽을 때 좀 더 꼼꼼하게 읽어야겠다는 생각을 했다.

일단 예제가 왜 저렇게 나오냐면
Step 1: 서류 기준 정렬

정렬 결과:
서류 면접
1 4
2 3
3 2
4 1
5 5

Step 2: 면접 기준 비교 (그리디)

첫 사람 (1, 4) → 무조건 뽑힘 → 기준 = 4 → ✅ count = 1
(2, 3) → 3 < 4 → 더 좋은 면접 → ✅ count = 2, 기준 = 3
(3, 2) → 2 < 3 → ✅ count = 3, 기준 = 2
(4, 1) → 1 < 2 → ✅ count = 4, 기준 = 1
(5, 5) → 5 > 1 → ❌ 탈락

최종 결과: 4명 뽑힘

테스트케이스 2
Step 1: 서류 기준 정렬

정렬 결과:
서류 면접
1 4
2 5
3 6
4 2
5 7
6 1
7 3

🔹 Step 2: 면접 기준 비교

(1, 4) → ✅ count = 1, 기준 = 4
(2, 5) → 5 > 4 → ❌
(3, 6) → 6 > 4 → ❌
(4, 2) → 2 < 4 → ✅ count = 2, 기준 = 2
(5, 7) → 7 > 2 → ❌
(6, 1) → 1 < 2 → ✅ count = 3, 기준 = 1
(7, 3) → 3 > 1 → ❌

최종 결과: 3명 뽑힘

    for document, interview in n_list:
        if not applicant:
            applicant.append((document, interview))
            standard = interview
        elif standard > interview:
            applicant.append((document, interview))
            standard = interview

해당 코드에서 서류 기준으로 정렬된 배열을 가지고 for문을 통해 서류와 면접을 각각 꺼내와 처음에 비어있는 합격 배열에 합격자를 넣고 합격자의 인터뷰 점수를 기준으로 잡는다.
다음 지원자는 인터뷰 기준보다 등수가 낮으면 탈락 등수가 높으면 면접과 인터뷰 결과 모두 떨어지지 않기 때문에 다음 지원자의 면접 점수를 다시 기준으로 잡는다.

import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    cnt = 1
    applicant = []
    n = int(input())
    n_list = [list(map(int, input().split())) for _ in range(n)]
    n_list.sort()
    
    for document, interview in n_list:
        if not applicant:
            applicant.append((document, interview))
            standard = interview
        elif standard > interview:
            applicant.append((document, interview))
            standard = interview

    print(len(applicant))