[Python] 1946 신입 사원

📌 문제

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

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

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

📌 입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

📌 출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

📌 문제 풀이

👨‍🏫 접근

가슴 아픈 문제다.

서류 순위와 면접 순위 둘 중 하나라도 순위가 앞서는 것이 있다면 신입사원으로 선발한다. 이때, 입력에서 중복 없이 순위를 입력받기 때문에 미리 정렬을 해두는 것이 좋다.

그렇게 해두면 서류 영역이나 면접 영역 둘 중에 하나만 입력을 받으면 되기 때문이다.

예를 들어서

5
3 2
1 4
4 1
2 3
5 5

의 입력은 정렬했을 때

1 4
2 3
3 2
4 1
5 5

이렇게 정렬할 수 있고, 서류영역은 이미 정렬이 되었기 때문에 차례대로 면접 영역 순위만 고려하면 된다. 오름차순으로 일단 서류영역에서 모두 첫째 사람보다 순위가 낮기 때문에 면접 영역의 순위가 높아야 신입사원으로 선발되기 때문이다.

그래서 for문을 통해 순회하여 답을 찾으면 된다. 하지만, 지원자의 숫자가 100,000까지 주어지기 때문에 이중 for문으로 최대 (n-1)n/2 만큼의 시간이 소요되고, O(n²) + O(n) => O(n²)의 시간 복잡도가 형성된다. 지원자의 숫자로 따지면 10억 초가 소요되어 문제의 제한인 2초를 훌쩍 넘는다. 그렇기 때문에 다른 방법을 강구해야 한다.

이때, 유용한 것이 계수정렬이다. 비록 지원자의 숫자는 높지만, for문을 한 번만 순회하면 돼서 시간 복잡도가 크게 줄어든다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
r = sys.stdin.readline

t = int(r())

def solve(n):
    s = [0] * (n + 1)
    for _ in range(n):
        x, y = map(int, r().split())
        s[x] = y

    MIN = n
    for i in range(1, n + 1):
        if MIN < s[i]:
            n -= 1
        else:
            MIN = min(MIN, s[i])
    return n

for _ in range(t):
    print(solve(int(r())))

📄 준비

import sys
r = sys.stdin.readline

t = int(r())

def solve(n):
    s = [0] * (n + 1)
    for _ in range(n):
        x, y = map(int, r().split())
        s[x] = y

카운팅을 받을 s를 n+1개의 길이로 받고, 각 입력을 받아 저장한다.

📄 풀이

    MIN = n
    for i in range(1, n + 1):
        if MIN < s[i]:
            n -= 1
        else:
            MIN = min(MIN, s[i])
    return n

순위의 최댓값은 n이므로 MIN의 값으로 n을 넣어준다.
1부터 n까지 순회하면서 MIN값보다 크다면 서류, 면접 순위 둘다 높은 것이기 때문에 n에서 차감한다.

📌 총평

시간 복잡도를 계산하는 것의 중요성을 알게 해준 문제. 그리디에서 어떻게 해야 할지 갈피를 잡고 있다.

 

처참한 시간 소요의 흔적...