[Algorithm] 백준 #1946 - 신입사원

맨 처음에 문제 이해가 안됐음...

입력하는 숫자들이 점수 라고 착각해서 잘못 풀고 있었다.. ㅂㅏ보...

 

점수가 아니라 순위를 입력한다!!

아래 그림처럼 순위를 적어주고, 합격자가 누구인지 옆에 표시하며 분류해줬다. 

 

 

 

 

 

 

 

 

 

 

 

1. 순위를 서류를 기준으로 먼저 오름차순 정렬을 해준다.
2. 서류 1등은 무조건 합격이므로, 서류 1등의 면접 순위를 rank변수에 저장해준다.
3. 아래로 내려가며 면접 순위를 비교해준다. (서류를 기준으로 오름차순 정렬을 했기에 서류 순위는 비교대상보다 무조건 낮기에 면접 순위만 비교해주면 된다.)
4.  (1 4)  (2 3) 을 비교하면, 면접 순위가 뒷사람이 더 높으므로 합격이다. 
5. 밑에 사람과 순차적으로 비교하며, 면접 순위가 더 높다면, 그 사람은 합격이므로 rank를 그사람의 순위로 업데이트 시켜준다.

rank순위를 업데이트 시켜줘야 그 다음 사람과 비교할 때 다시 rank를 사용할 수 있다.

 

 

 

1. 여기서도 동일하게, 일단 서류기준 오름차순 정렬을 해주고, rank변수에 4를 저장해준다.
2. 아래사람과 면접 순위를 비교해준다. (1 4), (2 5) 를 비교해주면, 아래사람의 면접순위가 더 낮으므로, 이 사람은 탈락이다. (=> rank는 그대로 둔다)
3. 다시 (1 4), (3, 6) 을 비교해준다. (=> 탈락이다. rank=4 로 그대로 있음)
4. (1 4), (4, 2) 비교 => 아래사람의 면접순위가 더 높으므로, 합격! rank = 2로 업데이트
5. 마지막 사람까지 비교해준다. 

 

<Solution>

import sys
T = int(sys.stdin.readline())

while T != 0:  # 0이되면 테스트 종료
    N = int(sys.stdin.readline())
    people = []
    cnt = 1  # 합격자 카운트! 서류 1위는 무조건 붙음
    for _ in range(N):
        num1, num2 = map(int, sys.stdin.readline().split())
        people.append([num1, num2])
    people.sort(key=lambda x: x[0])  #일단 서류 순위로 정렬
    rank = people[0][1]  # 서류 1위인 사람의 면접 순위를 넣어준다
    
    for i in range(1, N):
        if rank > people[i][1]:
            cnt += 1
            rank = people[i][1]
    print(cnt)
    T -= 1