77. Python 백준 1946 번 신입 사원 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그리디 알고리즘 문제인 1946 번 신입 사원 파이썬 자세한 설명입니다.

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

1946번: 신입 사원

 

 

먼저 백준 1946 번 파이썬 정답 코드입니다.

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T): #T번 반복
    cnt = 1
    n = int(input())
    grade = [0 for _ in range(n+1)]

    for _ in range(1, n+1):
        a, b = map(int, input().split())
        grade[a] = b

    Min = grade[1]

    for i in range(2, n+1):
        if grade[i] < Min:
            Min = grade[i]
            cnt += 1
    print(cnt)

 

 

서류 점수, 면접 점수 둘 중 하나만 남들보다 높다면 입사시키면 되므로

면접과 서류 점수를 모두 비교하여 남들보다 높은게 하나라도 있을 때 입사자 수를 1개씩 증가시키면 됩니다.

이때 점수가 아닌 ranking 으로 입력이 들어오므로

서류 점수를 index,

면접 점수를 value로 해서 입력을 받아봅시다.

그럼 자연스럽게 서류 점수순으로 정렬되어 면접 점수가 저장이 됩니다.

i 번째 지원자의 합불 여부는 어차피 서류 점수는 내림차순으로 정렬되어 있기 때문에

i - 1번째 지원자보다 어차피 낮고, 면접 점수가 높아야만 합격이 되므로

앞서 등장한 최소 면접 랭킹만 확인하여 i 번째 지원자의 랭킹이 높으면 합격입니다.

  

코드로 구현해봅시다.

시간 초과가 뜨므로 속도 향상을 위해 아래와 같은 코드를 넣고

import sys
input = sys.stdin.readline

 

T 번 반복하며

T = int(input())

 

cnt는 1, 

n은 입력

서류 점수를 index, 면접 점수를 value로 하는 list를 초기화 해줍니다.

cnt = 1
n = int(input())
grade = [0 for _ in range(n+1)]

 

서류 점수를 index, 면접 점수를 value로 값을 입력하여 list에 저장합니다.

for _ in range(1, n+1):
    a, b = map(int, input().split())
    grade[a] = b

 

이후  지금까지의 면접점수의 최저 랭킹은 서류 점수 1등 지원자의 점수로 초기화 한 후

Min = grade[1]

 

2번 지원자부터 검사하여 커트라인보다 랭킹이 높으면 커트라인을 업데이트 하고

(이후의 지원자들은 서류 점수에서 지고 있는 상황이므로 면접 점수에서 지면 합격할 수 없음)  

합격자수를 업데이트 한 후 출력해줍니다.

for i in range(2, n+1):
    if grade[i] < Min:
        Min = grade[i]
        cnt += 1
print(cnt)

 

 

Python 백준 1946 번 신입 사원 최종 코드입니다. 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T): #T번 반복
    cnt = 1
    n = int(input())
    grade = [0 for _ in range(n+1)]

    for _ in range(1, n+1):
        a, b = map(int, input().split())
        grade[a] = b

    Min = grade[1]

    for i in range(2, n+1):
        if grade[i] < Min:
            Min = grade[i]
            cnt += 1
    print(cnt)

 

지금까지 백준 1946 번 Python 코드와 자세한 설명이었습니다.

감사합니다.