📌 백준 1946번 - 신입 사원

📂 문제 유형

그리디 알고리즘 - 정렬

---

📌 문제 설명

서류 성적과 면접 성적 두 가지 기준으로만 인재를 선발하는 진영 주식회사.
한 명의 지원자가 다른 모든 지원자보다 두 성적이 모두 낮다면 탈락한다.
이때, 선발할 수 있는 신입 사원의 최대 수를 구하는 문제.

---

🧾 입력

• 첫 줄: 테스트 케이스 개수 T
• 각 테스트 케이스:
  • 첫 줄: 지원자 수 N
  • 이후 N개의 줄: 각 지원자의 (서류 성적 순위, 면접 성적 순위)

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

---

✅ 출력

각 테스트 케이스마다 선발 가능한 인원 수 출력

4
3

---

🧠 시험하는 개념

• 정렬 후 그리디하게 한 기준으로만 판단
• "서류 순위를 기준으로 정렬" 후, 면접 순위만 비교하면 됨
• 정렬 + 선형탐색으로 O(N log N)에 해결 가능

---

💻 내가 제출한 코드

import sys
input = sys.stdin.read

data = input().split()
i = 0
t = int(data[i])
i += 1

for _ in range(t):
    n = int(data[i])
    i += 1
    a = []
    for _ in range(n):
        d = int(data[i])
        m = int(data[i + 1])
        a.append((d, m))
        i += 2
    a.sort()

    cnt = 1
    min_m = a[0][1]

    for j in range(1, n):
        if a[j][1] < min_m:
            cnt += 1
            min_m = a[j][1]

    print(cnt)

---

📘 코드 설명

코드	설명
input = sys.stdin.read	빠른 입력 처리를 위해 전체 입력을 한번에 받아옴
data = input().split()	공백 기준으로 데이터 분리
a.sort()	서류 순위 기준 오름차순 정렬
min_m = a[0][1]	첫 번째 지원자의 면접 순위를 기준값으로 설정
if a[j][1] < min_m:	더 높은 면접 순위 발견 시만 선발
cnt += 1	선발 인원 수 증가

---

✅ 코드의 큰 그림

1. 서류 성적으로 정렬
2. 면접 성적이 앞선 사람보다 나은지 확인
3. 둘 중 하나라도 뒤처지지 않으면 선발

---

🧠 요약 정리

항목	내용
핵심 알고리즘	그리디, 정렬
핵심 아이디어	서류 성적으로 정렬 후, 면접 순위만 비교
시간 복잡도	O(N log N)
공간 복잡도	O(N)
입력 최적화	sys.stdin.read() 활용

---

📎 문제 링크

• 🔗 백준 1946번 - 신입 사원