[Python] BOJ / 1946번 / 신입 사원

1946번: 신입 사원

 

📝 문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

 

📜 풀이

• 각 지원자들의 성적을 특정 열(서류심사 성적, 면접시험 성적)을 기준으로 정렬하면 나머지 하나의 열만 비교함으로써 해당 지원자 선발될 수 있는지 아닌지를 판별할 수 있음
• 예로, (3, 2), (1, 4), (4, 1), (2, 3), (5, 5)로 입력이 주어진 경우 이를 1열을 기준으로 오름차순 정렬하면 다음과 같음

1 4

2 3

3 2

4 1

5 5

• 이때 1행에 해당하는 지원자의 경우 서류심사 성적을 1위로 받았기 때문에 면접시험 성적과 상관없이 무조건 선발될 수 있다.
• 2행부터는 서류심사 성적을 본인보다 높은 순위로 받은 지원자가 존재하기 때문에 다른 지원자와 면접시험 성적을 비교하여 두 성적 모두 다른 지원자보다 떨어지는지 확인해야한다.
• 이때, 만약 면접시험 성적의 순위가 현재 행의 윗 행들과 비교하여 하나라도 떨어진다면, 해당 지원자는 선발될 수 없는 지원자라는 것을 확인할 수 있다.

 

💻 소스코드

• 아래 코드는 시간 초과로 통과 실패한 코드이다.

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    score = [list(map(int, input().split())) for _ in range(n)]

    score.sort(key=lambda x: x[0])

    cnt = 0
    for i in range(n):
        for j in range(i):
            if score[i][1] > score[j][1]:
                cnt += 1
                break
    print(n - cnt)

• 위 코드에서 시간복잡도를 줄인 코드는 아래와 같다.

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    score = [list(map(int, input().split())) for _ in range(n)]

    score.sort(key=lambda x: x[0])

    low = 0
    ans = 1
    for i in range(1, n):
        if score[i][1] < score[low][1]:
            low = i
            ans += 1
    print(ans)