1946번: 신입 사원

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

 

---

이번에도 그리디 문제다.

바로 전 문제인 회의실 배정 문제와 거의 비슷한 문제라고 볼 수 있다.

 

그리고 문제 설명이 살짝 헷갈렸던 문제기도 하다.

지원자의 (서류심사 성적, 면접시험 성적)이 주어지는데, 둘 중 적어도 하나가 다른 지원자보다 떨어지지 않는 사람만이 선발 될 수 있다.

즉, A라는 인원의 (서류심사 성적, 면접시험 성적)이 임의의 인원 B의 (서류심사 성적, 면접시험 성적)보다 둘 다 떨어지는 경우가 하나라도 있다면, A는 뽑힐 수가 없는 것이다.

 

결국 정렬이 필요하다.

문제를 풀다 보니 그리디는 정렬과 항상 붙어 있는 느낌이다.

 

서류심사 성적 기준으로 오름차순 정렬한다.

그리고  면접시험 성적을 반복문을 돌면서 비교하면 된다.

 

만약, 반복문을 돌면서 현재 확인하는 사람의 면접 성적 순위가 비교 기준의 면접 성적 순위보다 큰 경우(숫자가 높으면 순위가 낮으므로, 성적이 낮은 것)에는 그 사람은 절대로 뽑힐 수가 없다.

그리고, 현재 확인하는 사람의 면접 성적 순위가 비교 기준의 면접 성적 순위보다 작은 경우에는 뽑힐 수 있다.

그 경우에는 선발하는 사람 수를 1 증가시켜주고, 비교 기준 면접 성적 순위를 확인한 사람의 면접 성적 순위로 바꿔준다.

이렇게 반복문을 N까지 한번 돌아주면 정답을 구할 수 있다.

 

---

# 1946번: 신입 사원
import sys
input = sys.stdin.readline
t = int(input()) # 테스트 케이스 수


while t:
    n = int(input()) # 지원자 숫자
    score = []
    for _ in range(n):
        each_score = list(map(int, input().split()))
        score.append(each_score)

    score.sort() # 서류 심사 성적 기준으로 오름차순 정렬
    
    cmp_rank = score[0][1] # 처음에 뽑는 면접 성적 순위
    cnt = 1 # 선발할 수 있는 신입 사원 수
    for i in range(1, n):
        if cmp_rank > score[i][1]: # 현재 확인하는 사람의 면접 성적 순위가 더 작은 경우에만 선발할 수 있다.
            cmp_rank = score[i][1] # 현재 선발한 사람의 면접 성적 순위로 비교 기준이 될 면접 성적 순위를 갱신한다.
            cnt += 1
    
    print(cnt)
    t -= 1

 

 

그리고 import sys를 활용해 input = sys.stdin.readline 코드를 안 넣으면 시간초과가 난다.

앞으로 다른 문제 풀때도 넣어줘야 할 듯 싶다.