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

문제링크: https://www.acmicpc.net/problem/1946

1946번: 신입 사원

시간 제한	메모리 제한	제출	정답	맞힌사람	정답 비율
2 초	256 MB	48355	16073	11720	32.110%

문제

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

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

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

입력

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

출력

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

 

 

 

 

 

 

풀이

---

이 문제는 정렬에 대한 새로운 시각이 있어야 풀 수 있는 문제이다.

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

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

 

이 문제를 풀때 생각을 해본 부분은 다음과 같다.

 

arr을 통해 값을 입력받는다고 했을 때 (list)

arr은 2차원 list로 나온다. 그리고 이 값을 1번째 원소기준으로 정렬하면 (1차면접, 2차면접이라고 하자 헷갈림..)

 

1차면접의 1위부터 n위까지의 순위로 정렬이 진행된다.

 

예를 들어보면 다음과 같다.

1, 3

2, 1

3, 2

이 부분에서 우리가 따져봐야 할 부분은 2번째 부분이다. 왜냐하면 일단 1차면접 순위에서 자기 순위보다 낮은 사람들을 살펴 볼 필요는 없기 때문이다. (적어도 하나이상의 점수가 높음)

 

이제부터는 우리가 봐야할 부분이 2번째부분을 어떻게 살펴봐야할 지 생각해야한다.

 

이때 나는 for문을 하나 더 써봤다.

for i in range(n):

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

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

 

2중for문을 썼지만 1+2+....+n의 형태로 나타나 결국 합이 n(n+1)/2의 형태가 나와 암튼 시간복잡도는 n**2이다. ㅜㅜ 이 부분에서 for문을 진짜 1개만 써야된다고 생각해 고민을 하기 시작했다.

 

 (한번 생각해보세요)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(두번 생각해보세요)

 

 

 

 

 

 

 

 

 

(세번 생각...) 

 

자 이제 어떻게 풀었는지 살펴보자!

 

여기서 나는 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(t):
    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)