[BOJ] 1946. 신입 사원

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

 

1. 해결방법

"""
1. 아이디어
- 성적을 입력받고 서류심사 등수를 기준으로 오름차순으로 정렬
- 순서대로 면접 순서를 비교하면서 count
- temp는 서류 1등을 변수로 저장
- temp와 비교해서 면접 등수가 더 높으면 count + 1
- count + 1 했을 떄, temp에는 비교한 면접 등수가 저장된다.
- 남은 인덱스와 위의 내용을 반복

2. 시간복잡도
- O(20 * 100000 * N)

"""

 

 

2. 정답코드

import sys
input = sys.stdin.readline

T = int(input())

for i in range(T):
    N = int(input())
    grades = sorted([list(map(int, input().split())) for _ in range(N)])

    count = 1
    temp = grades[0][1]

    for j in range(1, N):
        if temp > grades[j][1]:
            count += 1
            temp = grades[j][1]

    print(count)

이 문제는 내용을 이해하는게 제일 힘들다.
본인은 처음에 점수인지 등수인지도 구분하지 않고 풀었다가 광탈하고, 이해한 내용이랑 달라서 광탈했다.

주의해야될 점은 서류 등수든 면접 등수든 둘 중 하나만 앞의 사람 등수를 제치면 합격이다. 그러기 위해서는 먼저 서류 등수나 면접 등수를 정렬화하는 작업이 필요하다.
본인은 서류 등수를 정렬화 했다. 정렬을 했으면 면접 등수만 신경쓰면 되는데 서류 1등의 면접 등수와 서류 2등의 면접 등수를 비교하고 2등의 면접 등수가 더 높으면 합격. 서류 등수 3등은 그 서류 등수 2등과 면접 등수로 승부를 보게 된다. 이런 식으로 위에 등수는 반복적으로 일어난다.