문제 링크 : https://www.acmicpc.net/problem/1946
1. 아이디어
! 주의사항 : 주어진 값은 점수가 아니라 등수다
1) 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 선발되지 않는다
2. 해결방안
입력되는 2가지 값에 대해서 두 개 모두 나보다 등수가 높은 사람이 있으면 탈락하게 된다.
예를 들어 A가 서류심사와 면접에서 7등, 9등을 하고 B가 8등, 10등을 했다면 B는 탈락이다. 이 때는 다른 인원들에 대해 고려하지 않아도 무조건 탈락이다. 단 하나의 케이스만 존재하더라도 탈락이기 때문이다.
예를 들어 A가 서류심사와 면접에서 7등, 9등을 하고 B가 20등, 8등을 했다면 B는 합격을 보장받지는 않지만, A때문에 탈락하지는 않는다. 다른 사람들에 대해서도 비교해야한다.
위의 예에서 도출할 수 있는 것은 해결방안은 서류심사 또는 면접 등수로 정렬을 진행하는 것이다.
예를 들어 다음과 같은 테스트셋이 있다.
3 2
1 4
4 1
2 3
5 5
이 때 둘 중 하나의 값으로 정렬한다. 여기서는 앞에 있는 값인 서류심사 점수로 정렬을 하겠다.
1 4
2 3
3 2
4 1
5 5
각 전형의 등수가 1,4인 사람은 반드시 합격이다. 왜냐하면 하나의 전형에서 1등을 했다는 것은 해당 전형에서는 가장 점수가 높고, 나보다 점수가 높은 사람이 없으므로 합격 조건에 해당한다.
각 전형의 등수가 2,3인 사람은 합격이다. 판단 방식은 이 문제의 합격 조건과 동일하다. 우리는 서류 심사 성적으로 정렬을 진행했다. 서류 심사 성적으로 정렬했을 때 내가 2등이라고 한다면, 나의 합격 조건은 1등보다 면접 등수가 높아야하는 것이다. 서류 심사 1등의 면접 등수는 4위이며, 나의 면접 등수는 3위이므로 합격이다.
그 다음부터는 앞의 방식을 반복한다. 예를 들어 각 전형의 등수가 3,2인 사람은 내 앞에 있는 두 사람의 면접 등수와 나의 면접 등수를 비교해야 한다. 여기서 적용할 수 있는 방식은 2가지다
1) 서류 심사 1,2위에 대한 면접 등수를 차례대로 확인한다.
2) 내 앞에 있는 사람들의 면접 등수 중 가장 낮은 값을 기억하고 있다가 비교한다
1번의 방식으로 진행하는 경우 코드에 따라 시간초과가 발생하거나, 발생하지 않더라도 처리 시간이 길어진다.
2번의 방식으로 진행하는 경우 1번 방식보다 시간이 단축된다. 왜냐하면 매 순간마다 내 앞에 있는 모든 인원에 대해 검사하지 않고, 최소값만 기억하고 있다가 비교하면 되기때문이다. 최소값을 가지고 있는 이유는 나의 합격 조건은 내 앞에 있는 사람들보다 나의 면접 등수가 낮아야하기때문이다.
3. 풀이
n = int(input())
for i in range(n):
member = int(input())
failed = int(0) #탈락하는 사람
arr= [0 for i in range(member+1)]
# 1등부터 있는데 인덱스는 0부터 있으므로 보기 좋게 1부터 시작한다
for j in range(member):
index, value = map(int, input().split())
arr[index] = value
min = arr[1]
for j in range(2, member+1):
if min > arr[j]:
min = arr[j]
else:
failed += 1
print(member-failed)