(백준) 1946 (python Python) – 신입사원

문제

언제나 최고만을 목표로 하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다.

인재 선발 시험은 1차 서류 심사와 2차 면접 시험에서 실시됩니다.

최고만을 목표로 한다는 기업의 이념으로 그들은 최고의 인재만을 직원에게 선발하고 싶다.

그래서 진영주식회사는 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 한쪽이 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다.

즉, 한 응모자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 저하된 경우, A는 결코 선발되지 않는다.

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

입력

첫 번째 행에는 테스트 케이스의 수 T(1≤T≤20)가 주어집니다.

각 테스트 케이스의 첫 번째 행에는 지원자 수 N(1≤N≤100,000)이 주어집니다.

2행째부터 N행에는, 각각의 지원자의 서류 심사의 성적, 면접 성적의 순위가 공백을 사이에 두고 1행에 주어진다.

양성적 순위는 모두 1위에서 N위까지 동석차 없이 결정된다고 가정한다.

출력

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

풀

---

이 문제는 정렬의 새로운 관점이 없으면 해결할 수 없는 문제입니다.

우선 이 문제를 처음 풀 때 이중 for문을 이용해 접근했지만 시간 초과로 실패했다.

O(n**2)가 10만의 제곱이기 때문에 제한시간인 2초 이내에 풀 수 없었다.

이 문제를 해결할 때 생각한 부분은 다음과 같습니다.

arr을 통해 값을 받으려고 할 때 (list)

arr은 2차원 리스트로 나온다.

그리고이 값을 첫 번째 원소 기준으로 정렬하면 (1 차 면접, 2 차 면접으로 혼동합니다.

)

1차 면접의 1위에서 n위까지의 순위로 정렬이 이루어진다.

예를 들면 다음과 같습니다.

1, 3

2, 1

3, 2

이 부분에서 우리가 봐야 할 부분은 두 번째 부분이다.

왜냐하면 일단 1차 면접 랭킹에서 자기 랭킹보다 낮은 사람들을 볼 필요가 없기 때문이다.

(적어도 하나 이상의 점수가 높음)

이제부터 우리가 보아야 할 부분이 두 번째 부분을 어떻게 보아야 하는지 생각해야 합니다.

이때 나는 for문을 또 하나 사용해 보았다.

for i in range(n):

for j in range(i, -1, -1):

의 형태로 본인보다 1차 면접 순위가 높은 사람만을 비교하는 코드를 짠다.

이중 for문을 썼지만 1+2+….+n의 형태로 나타나 결국 합계가 n(n+1)/2의 형태가 나오고, 어쨌든 시간의 복잡성은 n**2 이다.

ㅜㅜ 이 부분에서 for문을 실제로 하나만 써야 한다고 생각해 고민을 시작했다.

(한 번 생각해보십시오)

(두 번 생각해보십시오)

(3번 생각…)

그럼 어떻게 해결했는지 보자!

여기서 나는 dp 개념인 메모화를 생각했다.

왜냐하면 우리가 비교해야 할 부분은 1차 면접 순위가 자신보다 높은 사람들의 2차 면접 순위다.

그러나 2차 면접 순위를 비교할 때 자신보다 높은 사람의 2차 면접 순위보다 높아야 하기 때문에

(자기보다 1차 높은 사람을 n이라고 하자) n의 2차 점수 최고 순위보다 높은 것만으로 좋다.

이것에 의해, tmp라고 하는 변수에 1차 면접 1 등의 2차 점수를 넣고, for문을 이용하여 n까지의 2차 점수만을 비교하면 된다.

tmp가 arr(i)(1)보다 높은 순위를 가지면 결과 값에 1을 더하여 tmp를 arr(i)(1)로 업데이트합니다.

(2차 면접 순위 최고점 갱신)

덧붙여서, arr(i)(1)은 1차 면접 i번째 순위의 2차 면접 점수입니다.

이대로 코드를 구현하면 시간의 복잡성도 O(n)로 문제를 해결할 수 있다!

오늘 게시 종료!

구현 코드

---

from sys import stdin
input = stdin.readline

t = int(input())
results = ()

for _ in range
    arr = ()
    n = int(input())
    res = 0
    for _ in range(n):
        arr.append(list(map(int, input().split())))
    arr.sort() # 정렬
    tmp = arr(0)(1) # 1차면접 1등의 2차면접 순위 -> 2등부터는 1면접순위 기준 해당 순위보다 높은 사람의 2차면접 순위보다 높은 점수를 받을 경우 정답조건 만족
    for i in range(1, n):
        if tmp > arr(i)(1): # 2차 면접 순위가 더 높기 때문에 조건 만족
            res+=1
            tmp = arr(i)(1) # 2차면접의 최고점수 변경
    results.append(res+1)

for result in results:
    print(result)