BOJ 1946 신입 사원

https://www.acmicpc.net/problem/1946
시간 2초, 메모리 256MB
input :

• T(1 ≤ T ≤ 20)
• 지원자의 숫자 N(1 ≤ N ≤ 100,000)
• 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다.

output :

• 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력

조건 :

• 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙

---

처음 문제를 제대로 안 읽은게 문제였다.
입력을 받았을 때 이 데이터는 '순위'를 나타내는 것이지, 점수가 아니다
그래놓으니까 1번 예제가 왜 4명인지 도당체 이해가 안 되었었다....

암튼 우리는 순위를 입력을 받을 것이다.
나의 경우에 서류 성적을 기준으로 오름차순 정렬을 해주고, interview_score 에 면접 성적을 저장 하도록 했다.

조건을 보았을 때 다음에 채용을 할 사원의 성적이 앞에서 채용된 모든 사람들 보다 면접 성적이 높아야 한다.
그래서 현재 interview_score보다 높은 사람(즉, 숫자는 적은 순위가 높은) 사람이 나오면 이 사람의 성적으로 업데이트를 해서 갈수록 순위 컷이 높아지도록 만들어 주자.

import sys

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    data = []
    for j in range(n):
        data.append(tuple(map(int, sys.stdin.readline().split())))

    data.sort()
    max_interview_rank = data[0][1]
    cnt = 1

    for j in range(1, n):
        inter = data[j][1]
        if inter < max_interview_rank:
            cnt += 1
            max_interview_rank = inter
    print(cnt)

나의 경우엔 당연히 그냥 정렬을 쓰자라는 생각이였는데
다른 분들의 경우에 서류 심사 성적 순위를 idx로 , 면접 심사 순위를 그 값으로 저장을 하게 해서 이용하는 방법을 썼다.. 와우 정렬을 하지 않고 정렬을 해버리는 또 하나 배웠다

import sys

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())
    data = [0] * (n + 1)
    for j in range(n):
        bio, interview = map(int, sys.stdin.readline().split())
        data[bio] = interview

    max_interview_rank = data[1]
    cnt = 1

    for j in range(1, n + 1):
        if data[j] < max_interview_rank:
            cnt += 1
            max_interview_rank = data[j]
    print(cnt)