[백준 1946] 신입사원

www.acmicpc.net/problem/1946

1946번: 신입 사원

---

문제 설명

1. 지원자 n명에 대한 [면접랭킹, 인터뷰랭킹]이 주어집니다.

2. 선별 기준은 다른 모든 지원자와 비교했을 때 적어도 하나의 랭킹은 남들보다 부족하지 않아야 합니다.

3. 최대한 많은 사람을 뽑았을 때 몇 명인지 제출해야 합니다.

 

알고리즘

1. "면접 랭킹" 또는 "인터뷰 랭킹" 중 하나를 오름차순으로 정렬한다.

  - 이 글에서는 면접 랭킹을 정렬한다. 

2. 면접 랭킹을 기준으로 정렬 후, 가장 앞에 있는 지원자는 선별이 확정된다. 

3. "선별이 확정된 지원자의 인터뷰 랭킹"과 "다음 지원자의 인터뷰 랭킹"과 비교합니다.

  - 다음 지원자의 랭킹이 높다면, 선별을 확정합니다

  - 그렇지 않다면, *선별하지 않습니다.

 

* 선별하지 않는 이유

선별된 지원자인 A[1, 4]와 선별되지 않은 지원자 B[2, 5]를 비교해보겠습니다.

- [2, 5] 중에 2는 면접랭킹을 가르키고, 5는 인터뷰랭킹을 가르킵니다.

 

B가 선별되기 위해서는 A와 비교하여 적어도 하나의 우수한 성적이 있어야 합니다.

 - B의 면접랭킹(2)은 A(1)보다 더 낮습니다.

 - B의 인터뷰랭킹(5)은 A(4)보다 더 낮습니다.

따라서 B는 선별되지 못합니다.

 

 

문제 특징

1. O(N)으로 해결해야 한다.

 - list.sort(), sorted()이 포함되면 시간초과가 나거나, 시간 효율성이 매우 떨어진다.

 따라서 리스트를 만들어서 인덱스를 면접 랭킹으로 사용하고, 인덱스 값을 인터뷰 랭킹으로 사용한다.

 

코드

import sys
# sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")

numCase = int(input())
for _ in range(numCase):
    numApplicants = int(input())
    ranks = [0] * (numApplicants + 1)
    for _ in range(numApplicants):
        doc, intvw = map(int, input().split())
        ranks[doc] = intvw

    cnt = 0
    last_intvw = numApplicants + 1
    for i in range(1, numApplicants+1):
        if ranks[i] < last_intvw:
            last_intvw = ranks[i]
            cnt += 1
    print(cnt)