[Python] 백준 1946 : 신입사원

문제

https://www.acmicpc.net/problem/1946

[ 문제 조건 ]

• 각 지원자마다 서류, 면점 순위를 입력 (* 주의 성적이 아니므로 순위가 낮은게 좋은거임)
• 서류, 면접 성적 중 적어도 다른 지원자보다 둘 중 하나 높아야 함
• → 즉, 다른 지원자보다 둘 다 낮으면 탈락

[ 해결순서 ]

1. 문제를 해결하는 포인트 중 하나가 입력 받은 후 먼저 1차적으로 서류순으로 등수를 정렬 하는 것이다. ( 면접 순으로 해도 상관 X )
2. 이미 서류 순으로 정렬 했다면, 이제는 면접 등수만 갖고 비교하면 되므로 훨씬 수월하다.
3. 먼저 기준 값으로 서류 1등의 면접 등수를 두고 값을 계산하는데, 이미 뒤에 지원자들은 서류 등수는 다 낮은데 면접 등수까지 낮으면 둘 다 낮은 것이므로 탈락
4. 기준 값보다 면접 등수가 높은 값이 나오면 result(선발 인원) +1 해주고
5. 다시 기준 값을 변경해야 한다. 왜냐?
6. 모든 지원자를 비교했을 때 어떤 지원자보다 둘 다 낮은 점수라면 탈락이므로,
7. 이미 앞 부분은 합격, 탈락자가 결정된 상태에서 해당 값보다 다음 지원자는 이미 서류는 낮으니 무조건 면접이 높아야 통과이다!

예제 풀이

✏️한줄평

: 그리디 알고리즘 개념은 알고 있었는데 문제로 푸니 새롭다. 은근 서류로 정렬을 먼저 하고 나머지 계산한다는 아이디어가 바로 나오지 않아 조금 시간이 걸렸다.

---

코드

	import sys
	input = sys.stdin.readline
	arr = []
	T = int(input())
	for _ in range(T):
	N = int(input())
	arr = [list(map(int, input().split())) for _ in range(N)] #서류, 면접 성적 입력
	# 서류 순으로 정렬
	arr.sort(key=lambda x: x[0])
	result = 1 #선발된 인원수 (서류 1등은 이미 선발)
	piv = arr[0][1] #서류 1등의 면접 등수가 기준으로 비교
	for i in range(1, N):
	if piv > arr[i][1]: #기준보다 면접등수가 높으면 (값이 작으면)
	result+=1
	piv = arr[i][1]
	print(result)

view raw BOJ1946.py hosted with ❤ by GitHub