[백준]1946번 신입 사원 - 그리디

 

import sys

t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())
    grade = [[0] * 2 for i in range(n)]
    cnt = 1
    for j in range(n):
        grade[j][0], grade[j][1] = map(int, sys.stdin.readline().strip().split())
    grade.sort(key=lambda x: int(x[0]))
    minV = grade[0][1]
    for x in range(n):
        if minV > grade[x][1]:
            minV = grade[x][1]
            cnt += 1
    print(cnt)

 

코드 설명

테스트 케이스의 숫자 만큼 반복문을 진행한다. 반복문 안에서 사원의 수를 입력받고 미리 0이라는 점수로 초기화 시킨다.

각 사원의 점수를 정하여 주고 서류심사의 성적이 높은 순으로 정렬한다. 1순위의 서류 심사 성적을 가진 사람의 면접 순위를 minV 라는 변수에 저장한다. 반복문을 돌며 minV 가 후 순위에 있는 사람의 순위보다 낮다면 minV 를 갱신하며 카운트를 해준다.

정답을 출력하며 마무리 한다.

 

Point : 먼저 한가지 성적을 기준(서류 심사)으로 순위를 정렬하여 준다. 1위의 서류 심사 성적을 가진 사람의 면접 순위보다 높은 순위를 가진 사람을 찾고 최솟값을 갱신해 나가며 카운트하면 최대 인원수를 구할 수 있다.

정렬된 리스트를 보고 정렬되지 않은 조건(면접 성적)을 보며 어떠한 규칙으로 인원이 선발되는지 면밀히 살펴보며 규칙을 찾아낼 수 있었다.