[백준 1946번] 신입사원 - 파이썬

문제 링크:

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

1946번: 신입 사원

 

문제 풀이:

• 이 문제의 핵심문장은 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙이다.
• 먼저 서류심사 순위를 기준으로 오름차순 정렬하자. 서류심사만 기준으로 하면 순위 1등을 제외한 나머지는 선발 대상이 아니다. 여기서 선발 인원수 1을 증가시킨다. (서류심사 1등은 무조건 선발되기 때문)
• 다음으로 면접시험 성적을 비교해보자. A라는 지원자의 면접 등수 숫자가 서류심사 1등의 면접 등수 숫자(Max) 보다 낮다면 A는 선발대상에 포함된다. 여기서 선발 인원수 1을 증가시키고 Max를 A의 등수로 받는다.

ex)

A: 1 4

B: 2 3

C: 3 2

1. A, B, C 참가자가 있다고 하자. 1열은 서류심사 순위, 2열은 면접심사 순위가 되겠다. A 지원자는 서류심사가 1등이므로 무조건 채용이 된다. (선발인원은 현재 1명)

2. 이제 A의 면접 순위를 가지고 다른 지원자들이 선발될 수 있는지 보자. A의 면접 순위가 4, B의 면접 순위가 3이다. B가 A보다 면접을 잘 봤기에 채용이 된다. (선발인원 +1)

3. B의 면접 순위를 가지고 다른 지원자들이 선발될 수 있는지 보자.  B가 3이고, C가 2이다. C가 B보다 면접을 잘 봤으므로 채용이 된다. (선발인원 +1)

면접 순위 잘 본 참가자를 다음 참가자와 비교해가면서 선발인원을 추가하면 된다.

 

• 채점 과정에서 시간 초과가 뜰 경우 input() 대신 sys.stdin.readline()을 이용하면 된다.

 

---

# 1946번 신입사원

import sys

t = int(input()) #테스트 케이스

for i in range(t):
    cnt = 1
    data = []
    
    n = int(input())
    for i in range(n):
        paper, interview = map(int,sys.stdin.readline().split())
        data.append([paper, interview])

    data.sort() # 서류 기준 오름차순 정렬
    Max = data[0][1]
    
    for i in range(1,n):
        if Max > data[i][1]:
            cnt += 1
            Max = data[i][1]

    print(cnt)

 

[백준 1946번] 신입사원 - 파이썬